图灵完备性

在可计算性理论，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟任何图灵机，那么它便符合图灵完备（Turing-complete或computationally universal）。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。

关于该术语在预言机的相对可计算性理论中的用法，请见“图灵归约”。

还有一个相关概念是图灵等价 – 如果P可以模拟Q并且Q可以模拟P，则两台计算机P和Q称为等效计算机。 邱奇－图灵论题认为任何可以通过算法计算其值的函数都可以由图灵机计算，因此，如果任何真实世界的计算机都可以模拟图灵机，则其对图灵机是图灵等价的。 通用图灵机可用于模拟任何图灵机，且可以扩展现实世界计算机的计算方面。^{[NB 1]}

如果某物是图灵完备的，则它可以用于模拟某些图灵完备的系统。例如，一个指令式编程具有条件表达式（例如，“ if”和“ goto”语句，或者“branch if zero”的指令；请参见单一指令计算机）并且具有更改任意指令的能力，那么它便具备图灵完备性。

需要注意的是，虽然任何物理系统都不可能进行无限的迭代展开，但如果忽略这项限制，绝大多数物理系统都符合图灵完备性。

非数学应用

在口语用法中，术语“图灵完备性”或“图灵等价”用于表示任何现实世界通用计算机或计算机语言都可以近似模拟任何其他现实世界通用计算机的计算方面、用途的计算机或计算机语言。

到目前为止构建的现实计算机可以在功能上进行分析，就像单带图灵机（对应于它们的内存的“带”）一样； 因此，相关的数学问题可以通过足够抽象的运算来应用。但是，现实计算机的物理资源有限，因此它们仅是线性有界自动机。与之对应的，通用计算机被定义为具有图灵完备的指令集，无限内存和无限可用时间的设备。

正式定义

在计算理论中，有几个密切相关的术语用于描述系统的计算能力。（比如抽象机器或者程序语言。）

图灵完全

一个计算系统可以计算任何图灵-可计算函数，被称作图灵完全（或者图灵完备）。或者任何可以模拟通用图灵机的系统。

图灵等价

如果一个计算系统可以计算的所有函数都是图灵可计算的，则称他为图灵等价系统。这个系统可以计算的函数和通用图灵机可以计算的是同一类，或者这个系统可以模拟通用图灵机并被模拟。（所有已知的图灵完备系统都是图灵等价的，这为邱奇-图灵论题提供了支持。）

（计算）通用性

如果一个系统可以计算一个类别的其他系统可以计算的每个函数（或可以模拟这个类别的每个系统），则该系统相对于这类系统称为通用系统。 通常，通用性这一术语是针对图灵完备类的系统默认使用的。 术语“弱通用性”有时用于区分仅通过修改图灵机的标准定义才能实现其通用性的系统（例如细胞自动机）。

历史

可计算性理论

主条目：可计算性理论

可计算性理论使用计算模型来分析问题，并确定它们是否可计算，以及在什么情况下可计算。可计算性理论的第一个结果是：存在一类问题，使一个（图灵完备）的系统在一个任意长的时间后进行什么操作，不可能被预测到。

一个经典的例子是停机问题：创建一种算法来作为图灵完备语言的程序的输入，并给该程序提供一些数据，来确定程序处理输入后会最终停止或永远继续下去。对于某些输入，创建这样的算法微不足道，但总体上来说创建这种算法是不可能的。对于程序最后输出具有的任何特征，无法确定这种特征是否能保持。

这种不可能性给分析真实世界的计算机程序带来了问题。例如，没人可以编写一种工具，来防止程序员写出死循环，或者防止用户提供使程序死循环的输入。

相反，可以限制程序的运行时间（时限）或者限制流程控制语句的使用（例如，只提供迭代已知数组内部元素的循环）。然而另一种定理说明，存在能够被图灵完备语言解决的问题，却不能被任何循环能力受限的语言（即保证程序最后都会停止的语言）解决，因此所有这样的语言都是图灵不完备的。例如，一种保证程序完整运行并停止的语言，不能通过该语言内的所有可计算函数，来计算对角论证法中的可计算函数。

预言机

主条目：预言机

具有预言磁带的计算机可能比图灵机更强大：例如，磁带可能包含停机问题或其他一些图灵不可计算问题的解决方案。甚至具有随机预言机也是不可计算的（几乎必然），因为只有可数的计算而无数的预言。 因此，具有随机预言机的计算机可以计算出图灵机无法执行的操作。

数字物理学

主条目：邱奇-图灵论题

所有已知的物理定律都具有可通过数字计算机上的一系列近似值计算的结果。 一种称为数字物理学的假设指出，这并非偶然，因为宇宙本身可以在通用图灵机上计算。 这意味着无法在物理上构建比通用图灵机更强大的计算机。

例子

非图灵完备语言

存在很多并不图灵完备的语言，比如由正则表达式表示的正则语言，通过有限状态机进行识别。下推自动机和上下文无关文法更强大，但仍不是图灵完备的，他们一般用于在程序编译的初期阶段生成分析树。其他示例包括嵌入在Direct3D和OpenGL扩展名中的像素着色器语言的某些早期版本。^{[来源请求]}

在如Charity和Epigram之类的总函数式编程语言中，所有功能都是总的，必须终止。 Charity使用类型系统和基于范畴论的控制流程，而Epigram使用依赖类型。 LOOP语言的设计使其仅计算原始递归函数。 所有这些都计算总可计算函数的正确子集，因为总的总可计算函数集不可计算。 同样，由于这些语言的所有功能都是合计的，因此与图灵机相比，用于递归可枚举集合的算法无法用这些语言编写。

尽管无类型λ演算是图灵完备的，但简单类型λ演算不是。

数据语言

XML，HTML，JSON，和YAML不符合图灵完备性，因为他们通常用来表示结构化数据而不描述计算。这些语言有时被称为标记语言，或更恰当地称为“容器语言”或“数据描述语言”。

参见

• 克莱尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯纳–罗宾逊定理
• 跳跃逆转定理
• 算法信息论
• 乔姆斯基谱系
• 邱奇－图灵论题
• 可计算性理论
• 控制流程
• 判定器
• 莱斯定理
• 结构化程序理论
• 图灵焦油坑

注释

1. A UTM cannot simulate non-computational aspects such as I/O.

参考文献

相关阅读

• Brainerd, W. S.; Landweber, L. H. Theory of Computation. Wiley. 1974. ISBN 0-471-09585-0.
• Giles, Jim. Simplest 'universal computer' wins student $25,000. New Scientist. 24 October 2007 [2020-07-04]. （原始内容存档于2015-05-31）.
• Herken, Rolf (编). The Universal Turing Machine: A Half-Century Survey. Springer Verlag. 1995. ISBN 3-211-82637-8.
• Turing, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem (PDF). Proceedings of the London Mathematical Society. 2. 1936, 42: 230–265 [2020-07-04]. doi:10.1112/plms/s2-42.1.230. （原始内容存档 (PDF)于2020-11-30）.
• Turing, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem: A correction. Proceedings of the London Mathematical Society. 2. 1938, 43: 544–546. doi:10.1112/plms/s2-43.6.544.

外部链接

• Turing Complete. wiki.c2.com. [2020-07-04]. （原始内容存档于2016-10-07）.