亲爱的MBA智库百科用户:


过去的17年,百科频道一直以免费公益的形式为大家提供知识服务,这是我们团队的荣幸和骄傲。 然而,在目前越来越严峻的经营挑战下,单纯依靠不断增加广告位来维持网站运营支出,必然会越来越影响您的使用体验,这也与我们的初衷背道而驰。 因此,经过审慎地考虑,我们决定推出VIP会员收费制度,以便为您提供更好的服务和更优质的内容。


MBA智库百科VIP会员,您的权益将包括: 1、无广告阅读; 2、免验证复制。


当然,更重要的是长期以来您对百科频道的支持。诚邀您加入MBA智库百科VIP会员,共渡难关,共同见证彼此的成长和进步!



MBA智库百科项目组
2023年8月10日
百科VIP
未登录
无广告阅读
免验证复制
支付方式:
微信支付
支付宝
PayPal
购买数量:
1
应付金额:
10
汇率换算:
10
美元(USD)

按当月汇率换算,

包含手续费

打开手机微信 扫一扫继续付款
立即开通
PayPal支付后,可能会遇到VIP权益未及时开通的情况,请您耐心等待,或者联系百科微信客服:mbalib888。
温馨提示:当无法进去支付页面时,可刷新后重试或更换浏览器
开通百科会员即视为同意《MBA智库·百科会员服务规则》

支付成功

全球专业中文经管百科,由121,994位网友共同编写而成,共计436,064个条目

图灵完备语言

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

  2025 年 02 月 18 日 星期二

中文名称
图灵完备语言
语言特征
具有图灵完备性
汉语拼音
Túlíng Wánbèi Yǔyán
包  括
过程式语言、面向对象语言、多范式语言、
英文名称
Turing-complete language
深奥的语言等

目录

[隐藏]

概述

  如果一个计算机语言具有图灵完备性Turing Completeness),那么这个语言就是图灵完备语言Turing-complete language)。


背景

艾伦·图灵

  艾伦·麦席森·图灵Alan Mathison Turing,1912.6.23 - 1954.6.7),英国数学家、逻辑学家、密码学家和英国首位计算机科学家,被誉为计算机科学和人工智能之父。

  他对计算机科学的发展有着很高的影响力,他用图灵机提供了算法和计算概念的形式化,图灵机可以被视为通用计算机的模型。他的图灵测试对人工智能的发展,作出了重要的、典型的、具挑战性的和持久的贡献。

图灵机

图灵机模型
放大
图灵机模型

  在 1928 年第八届国际数学家大会上,德国数学家希尔伯特(David Hilbert,1862 - 1943)提出了关于数学的三个精辟问题:

  • First, was mathematics complete …(数学是完备的吗?)
  • Second, was mathematics consistent …(数学是一致的吗?)
  • And thirdly, was mathematics decidable ?(数学是可判定的吗?)

  希尔伯特的第三个问题又被称为判定性问题(Entscheidungsproblem)。为了证否这个命题,1936 年,图灵发表了一篇论文,题为《论可计算数,及其在判定性问题上的应用》(On Computable Numbers, with an Application to the Entscheidungsproblem)。在这篇论文里,图灵提出了一种假设的计算装置,他称之为 A-Machine(Automatic Machine,自动机器),这就是图灵机Turing Machine)。

可计算函数

艾伦·麦席森·图灵
放大
艾伦·麦席森·图灵

  1938 年,在美国普林斯顿大学攻读博士学位的图灵,发表了一篇博士论文,题为《基于序数的逻辑系统》(Systems of Logic Based on Ordinals)。在这篇论文里,图灵定义了可计算函数Computable function):

  • A function is effectively calculable if its values can be found by some purely mechanical process.
  • 如果一个函数的值可以通过某种纯机械的过程找到,那么这个函数就可以有效地计算出来。

  在作为特定计算模型的图灵机上产生的可计算函数,就被称为图灵可计算函数

图灵完备性

  如果一个计算系统可以计算每一个图灵可计算函数,那么这个系统就是图灵完备的;或者说,这个系统可以模拟通用图灵机。

  图灵完备性也可以用来描述计算机语言的计算能力。


定义

图灵完备语言
放大
图灵完备语言

  具有图灵完备性的计算机语言,就被称为图灵完备语言。绝大多数的编程语言,都是图灵完备语言。这包括:

  • 广泛使用的所有通用语言:
    • 过程式语言,如 FORTRAN、Pascal 等。
    • 面向对象语言,如 Java、Python 等。
    • 多范式语言,如 Ada、C++ 等。
  • 使用不太常见范式的大多数语言:
    • 函数式语言,如 Haskell、Mercury 等。
    • 逻辑式语言,如 Logtalk、Prolog 等。
    • 声明式语言,如 SQL、XSLT 等。
    • 深奥的语言(Esoteric programming language),一种奇特的数学娱乐形式,程序员用极其困难但数学上图灵等价的语言来实现基本的编程结构。


非图灵完备语言

  并非所有的计算机语言都是图灵完备的,例如标记语言,或者更恰当地称为“容器语言”或“数据描述语言”,就不是图灵完备的。

  非图灵完备语言Non-Turing-complete language),包括 HTML、JSON、XML、YAML 等。

本条目对我有帮助11
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目投诉举报

本条目由以下用户参与贡献

M id ca0e1820b225ab1ad414f1d3c9d4b121,Llyn.

评论(共0条)

提示:评论内容为网友针对条目"图灵完备语言"展开的讨论,与本站观点立场无关。

发表评论请文明上网,理性发言并遵守有关规定。

打开APP

以上内容根据网友推荐自动排序生成

官方社群
下载APP
告MBA智库百科用户的一封信
亲爱的MBA智库百科用户: 过去的17年,百科频道一直以免费公益的形式为大家提供知识服务,这是我们团队的荣幸和骄傲。 然而,在目前越来越严峻的经营挑战下,单纯依靠不断增加广告位来维持网站运营支出,必然会越来越影响您的使用体验,这也与我们的初衷背道而驰。 因此,经过审慎地考虑,我们决定推出VIP会员收费制度,以便为您提供更好的服务和更优质的内容。 MBA智库百科VIP会员(9.9元 / 年,点击开通),您的权益将包括: 1、无广告阅读; 2、免验证复制。 当然,更重要的是长期以来您对百科频道的支持。诚邀您加入MBA智库百科VIP会员,共渡难关,共同见证彼此的成长和进步!
MBA智库百科项目组
2023年8月10日

闽公网安备 35020302032707号

添加收藏

    新建收藏夹

    编辑收藏夹

    20