图灵完备性

在可计算性理论中，如果一个数据操作规则系统（例如计算机的指令集、编程语言或元胞自动机）可以用来模拟任何图灵，则它被认为是图灵完备的或计算通用的 机器（由英国数学家和计算机科学家艾伦图灵设计）。 这意味着该系统能够识别或决定其他数据操作规则集。 图灵完备性被用作表达这种数据操作规则集的力量的一种方式。 今天几乎所有的编程语言都是图灵完备的。

一个相关的概念是图灵等价——如果 P 可以模拟 Q 并且 Q 可以模拟 P，则两台计算机 P 和 Q 被称为等价的。Church-Turing 论文推测任何其值可以由算法计算的函数都可以由 图灵机，因此如果任何现实世界的计算机都可以模拟图灵机，那么图灵就等同于图灵机。 通用图灵机可用于模拟任何图灵机，并通过扩展任何可能的现实世界计算机的计算方面。

要表明某个东西是图灵完备的，只要表明它可以用来模拟某个图灵完备的系统就足够了。 没有物理系统可以拥有无限内存，但如果忽略有限内存的限制，大多数编程语言在其他方面都是图灵完备的。

在口语中，术语图灵完备和图灵等价物用于表示任何现实世界的通用计算机或计算机语言都可以近似模拟任何其他现实世界的通用计算机或计算机语言的计算方面。 在现实生活中，这导致了计算虚拟化和仿真的实用概念。

到目前为止构建的真实计算机可以像单磁带图灵机一样进行功能分析（磁带对应于它们的内存）； 因此，相关的数学可以通过将它们的操作抽象得足够远来应用。 然而，真实计算机的物理资源有限，因此它们只是线性有界自动机完备。 相比之下，通用计算机被定义为具有图灵完备指令集、无限内存和无限可用时间的设备。

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

图灵完备性 可以计算每个图灵可计算函数的计算系统称为图灵完备（或图灵强大）。 或者，这样的系统是一个可以模拟通用图灵机的系统。图灵等价一个图灵完备系统被称为图灵等价，如果它可以计算的每个函数也是图灵可计算的； 即，它计算与图灵机完全相同的函数类别。 或者，图灵等效系统是可以模拟通用图灵机并被通用图灵机模拟的系统。 （所有已知的物理上可实现的图灵完备系统都是图灵等价的，这增加了对 Church-Turing 论点的支持。）（计算的）普适性如果一个系统可以计算系统可计算的每个函数，那么它就被称为关于一类系统的普适系统 在那个类中（或者可以模拟每个系统）。 通常，术语“通用性”默认用于图灵完备类系统。 术语弱通用有时用于区分系统（例如元胞自动机），其通用性仅通过修改图灵机的标准定义以包含具有无限多个 1 的输入流来实现。

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

Charles Babbage 的分析引擎（1830 年代）如果在设计时就已建成，那将是xxx台图灵完备机器。 巴贝奇赞赏这台机器能够进行出色的计算，包括原始逻辑推理，但他并不认为没有其他机器可以做得更好。 从 1830 年代到 1940 年代，加法器和乘法器等机械计算器被建造和改进，但它们不能执行条件分支，因此不是图灵完备的。

在 19 世纪后期，利奥波德·克罗内克 (Leopold Kronecker) 阐述了可计算性的概念，定义了原始递归函数。