圖靈完備性

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

还有一个相关概念是图灵等价 – 如果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. . Wiley. 1974. ISBN 0-471-09585-0.
    • Giles, Jim. . New Scientist. 24 October 2007 [2020-07-04]. （原始内容存档于2015-05-31）.
    • Herken, Rolf (编). . Springer Verlag. 1995. ISBN 3-211-82637-8.
    • Turing, A. M. (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. . Proceedings of the London Mathematical Society. 2. 1938, 43: 544–546. doi:10.1112/plms/s2-43.6.544.

    外部链接
    • . wiki.c2.com. [2020-07-04]. （原始内容存档于2016-10-07）.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.