图灵完整

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

到目前为止构建的真正的计算机可以像单带图灵机一样进行功能分析(“带”对应于它们的存储器)。因此，相关的数学可以通过将它们的运算高度抽象来应用。然而，真正的计算机有有限的物理资源，所以它们只是线性有界自动机完备的。相反，通用计算机被定义为具有图灵完整指令集、无限内存和无限可用时间的设备。

在可计算性理论中，几个密切相关的术语被用来描述计算系统(例如抽象机器或编程语言)的计算能力：

图灵完备性

可以计算每个图灵可计算函数的计算系统被称为图灵完备(或图灵强大)。或者，这样的系统可以模拟通用图灵机。

图灵等价

一个图灵完备系统被称为图灵等价系统，如果它能计算的每个函数都是图灵可计算的；也就是说，它计算的函数类与图灵机完全相同。换言之，图灵等价系统可以与通用图灵机相互模拟。(所有已知的图灵完备系统都是图灵等价的，这为丘奇-图灵论题增加了支持。)

(计算)通用

如果一个系统能计算出该类系统可计算的每一个函数(或能模拟每一个系统)，那么这个系统就被称为通用系统。一般来说，普适性这个术语是相对于图灵完备系统而言的。术语“弱通用”有时用于区分一个系统(例如细胞自动机)，其通用仅通过修改图灵机的标准定义来实现，以便包括具有无限多个1的输入流。

如果一个系统能计算出该类系统可计算的每一个函数(或能模拟每一个系统)，那么这个系统就被称为通用系统。一般来说，普适性这个术语是相对于图灵完备系统而言的。术语“弱通用”有时用于区分一个系统(例如细胞自动机)，其通用仅通过修改图灵机的标准定义来实现，以便包括具有无限多个1的输入流。

图灵完备性的意义在于，计算设备的每一个真实世界的设计都可以由通用图灵机来模拟。丘奇-图灵论题指出，这是一个数学定律——原则上，通用图灵机可以执行任何其他可编程计算机可以执行的任何计算。这与编写程序所需的工作量、机器执行计算所需的时间以及机器可能拥有的与计算无关的任何能力都无关。

查尔斯•巴贝奇的分析引擎(19世纪30年代)如果是在设计时制造的话，将会是第一台图灵完备的机器。巴贝奇意识到这台机器有巨大的计算能力，包括原始的逻辑推理，但他不认为没有其他机器能做得更好。从19世纪30年代到20世纪40年代，机械计算机器如加法器和乘法器被建立和改进，但它们不能执行条件分支，因此不是图灵完备的。

19世纪末，Leopold Kronecker提出了可计算性的概念，定义了原始递归函数。这些函数可以通过死记硬背计算来计算，但是它们不足以构成通用计算机，因为计算它们的指令不允许无限循环。20世纪初，David Hilbert领导了一个程序，用精确的公理和精确的逻辑推理规则来公理化所有的数学，这些规则可以由机器来执行。很快，很明显，一个小的演绎规则集足以产生任何公理集的结果。Kurt Gödel在1930年证明了，这些规则足以产生每个定理。

从哥德尔的不完全性定理开始，计算的实际概念很快就被孤立了。这个定理表明公理系统在推导其定理的计算推理时是有限的。丘奇和图灵独立地证明了希尔伯特的Entscheidungsproblem(决策问题)是不可解的，^[1] 从而确定了不完备性定理的计算核心。这项工作，连同哥德尔关于一般递归函数的工作，建立了简单指令的集合，这些集合在一起，能够产生任何计算。哥德尔的工作表明，计算的概念本质上是唯一的。

1941年，Konrad Zuse完成了Z3(计算机)，第一台工作的图灵整机；这是现代意义上的第一台数字计算机。^[2]

可计算性理论将问题描述为有或没有计算解。可计算性理论的第一个结果是，存在无法预测(图灵完备的)系统在任意长时间内会做什么的问题。

经典的例子是停机问题：创建一个算法，该算法以(a)某种图灵完全语言的程序，和(b)要馈送给该程序的一些数据作为输入；并且它决定了根据输入操作的程序是最终停止还是永远继续。创建一个可以对某些输入进行这种操作的算法是微不足道的，但一般来说是不可能的。对于程序最终输出的任何特征，都不可能确定这个特征是否成立。

这种不可能性在分析现实世界的计算机程序时会带来问题。例如，不能编写一个完全保护程序员不编写无限循环的工具，也不能保护用户不提供会导致无限循环的输入。

相反，可以将程序限制为仅在固定时间段内执行(超时)，或者限制流控制指令的能力(例如，仅提供对现有数组项进行迭代的循环)。然而，另一个定理表明，图灵完备语言可以解决一些问题，这些问题不能由任何只有有限循环能力的语言来解决（即任何保证每个程序最终都会停止的语言）。所以任何这样的语言都不是图灵完备的。例如，一种保证程序完成和停止的语言不能计算由该语言中所有可计算函数上的Cantor对角论生成的可计算函数。

可以访问无限数据磁带的计算机可能比图灵机更强大：例如，磁带可能包含停机问题的解决方案，或者其他一些图灵不可判定的问题。这种无限的数据磁带被称为图灵预言。即使有随机数据的图灵预言也是不可计算的(概率为1)，因为只有可数的许多计算，却有不可数的预言。所以一台带有随机图灵预言的计算机可以计算图灵机无法计算的东西。

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

作为图灵完全系统讨论的计算系统(代数，演算)是那些旨在研究理论计算机科学的系统。它们的目的是尽可能简单，以便更容易理解计算的极限。这里有几个：

• 自动机理论
• 形式语法(语言生成器)
• 形式语言(语言识别器)
• λ演算
• 后置图灵机
• 过程演算

大多数编程语言，传统的和非常规的，都是图灵完备的。这包括：

• 广泛使用的所有通用语言
  • 程序编程语言，如C、Pascal。
  • 面向对象的语言，如Java、Smalltalk或C#。
  • 多范式语言，如Ada、C++、通用Lisp、Object Pascal、Python、R。
• 大多数语言使用不太常见的范式
  • 函数语言，如Lisp和Haskell。
  • 逻辑编程语言，如Prolog。
  • 通用宏处理器，如m4。
  • 声明性语言，如XSLT。^[3]
  • 深奥的编程语言，一种数学再创造的形式，在这种形式中，程序员用一种极其困难但数学上图灵等价的语言来解决如何实现基本的编程结构。

一些重写系统是图灵完备的。

图灵完备性是能力的抽象陈述，而不是用于实现该能力的特定语言特性的规定。用于实现图灵完备性的特性可能会有很大不同；Fortran系统将使用循环结构，甚至可能使用goto语句来实现重复；Haskell和Prolog几乎完全没有循环，它们将使用递归。大多数编程语言都描述冯•诺伊曼体系结构上的计算，该体系架构有内存(RAM和寄存器)和控制单元。这两个元件使这个体系结构图灵完备。即使是纯函数语言也是图灵完备的。

声明性SQL中的图灵完备性是通过递归公共表表达式实现的。毫不奇怪，对SQL的过程扩展(PLSQL等)也是图灵完备的。这说明了为什么相对强大的非图灵完备语言很少出现的一个原因：语言的初始功能越强，它所应用的任务就越复杂，并且它的不完备性越早被认为是一个缺点，这鼓励其扩展直到图灵完备。

非类型λ演算是图灵完备的，但是许多类型λ演算包括系统F，不是图灵完备的。类型化系统的价值是基于它们能够在检测更多错误的同时代表最典型的计算机程序。

规则110和康威的生命游戏都是细胞自动机，都是图灵完全的。

7.1 无意的图灵完备性

一些游戏和其他软件是偶然满足图灵完备的。

电子游戏：

• 矮人要塞^[4]
• 《我的世界》^[5]
• 扫雷舰^[6]
• 小行星^[5]

纸牌游戏：

• 魔法:聚会^[5][7]

零人游戏(模拟)：

• 康威的生活游戏^[8][9]

计算机硬件：

• x86 MOV指令^[10]

有许多计算语言不是图灵完备的。其中一个例子是正则语言的集合，它们由正则表达式生成，并由有限自动机识别。有限自动机的一个更强大但仍然不是图灵完全的扩展是下推自动机和上下文无关文法的范畴，它们通常用于在程序编译的初始阶段生成解析树。进一步的例子包括嵌入在Direct3D和OpenGL扩展中的一些早期版本的像素着色器语言。

在所有函数式编程语言中，如Charity 和 Epigram，所有函数都是总的，必须终止。 Charity使用基于范畴理论的类型系统和控制结构，而 Epigram使用依赖类型。循环语言的设计使其只计算原始递归函数。所有这些计算全部可计算函数的适当子集，因为全部可计算函数的全部集合是不可计算枚举的。此外，由于这些语言中的所有函数都是总计的，递归可枚举集的算法不能用这些语言编写，这与图灵机不同。

虽然(非类型化)λ演算是图灵完备的，但简单类型λ演算不是。

8.1 数据语言

图灵完备性的概念不适用于XML、HTML、JSON、YAML和S表达式等语言，因为它们通常用于表示结构化数据，而不是描述计算。这些语言有时被称为标记语言，或者更恰当地被称为“容器语言”或“数据描述语言”。然而，规则110，一个图灵完全元胞自动机，已经在CSS 3中成功实现，从而在一定程度上证明了它的图灵完备性。^[11]

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