什么是图灵完备性？

Question

"Turing Complete"这个表达式的意思是什么？

你能简单地解释一下，不涉及太多理论细节吗？

- dlinsin

---

这个SO问题里有一些非常好的链接：https://dev59.com/DHRC5IYBdhLWcg3wJNqf。 - Lazer

...以及什么不是TC。干杯~ - jiyinyiyong

Answer 1

这是最简要的解释：

Turing完备系统指的是一个能够编写程序以找到答案的系统（尽管对于运行时间或内存没有任何保证）。

所以，如果有人说“我的新东西是Turing完备的”，这意味着原则上它可以用来解决任何计算问题（虽然通常并非如此）。

有时这也是个笑话……有个人在vi编辑器中编写了一个图灵机模拟器，因此可以说vi是世界上唯一需要的计算引擎。

- Mark Harrison

---

请参阅《图灵注释》以获取更多阅读内容。非常易懂。http://www.amazon.com/Annotated-Turing-Through-Historic-Computability/dp/0470229055/ref=sr_1_1?ie=UTF8&s=books&qid=1242667155&sr=8-1 - i_am_jorf

“often not in practice”这个说法是不正确的。因为没有一个可实现的系统拥有无限的纸带，所以在实践中不存在任何一个系统是真正的图灵完备的。我们真正意思想表达的是一些系统可以在其可用内存的极限范围内近似地实现图灵完备性。 - Shelby Moore III

但 Vi 是世界上唯一需要的计算引擎...;-) - Joe Edgar

Emacs也是一台图灵机吗？XD - alem0lars

最近有人证明了 PowerPoint 也是图灵完备的。 - Tagc

Answer 2

以下是简单的解释

Alan Turing 创造了一台机器，可以接收一个程序、运行它，并显示出结果。但是他需要为不同的程序创建不同的机器。因此，他创造了“通用图灵机”，可以接收任何程序并运行。

编程语言类似于这些机器（虚拟机）。它们接受程序并运行。现在，如果一个编程语言可以运行图灵机器所能运行的所有程序（无论使用哪种语言），那么它被称为“图灵完备”。

例如：假设有一个程序接受10个数字并将它们相加。图灵机很容易运行这个程序。但是，如果由于某种原因你的编程语言不能执行相同的加法运算，这将使它成为“图灵不完备”（就是这样说的）。另一方面，如果它可以运行任何通用图灵机能够运行的程序，则它是图灵完备的。

大多数现代编程语言（如Java、JavaScript、Perl等）都是图灵完备的，因为它们都实现了运行程序所需的所有功能，例如加法、乘法、if-else条件语句、返回语句、存储/检索/清除数据的方法等等。

更新：你可以在我的博客文章中了解更多信息：“JavaScript是图灵完备的” - 解释

- Raja Rao

---

当我想起图灵和其他早期计算机科学家每次想解决一个特定的问题都要构建一台特定的机器，这种机器需要专门术语来描述，这个想法就更有意义了。我们现在习惯了可以无限重新编程的一台机器。谢谢你提供的背景信息，Raja。 - Jacob Ford

JavaScript如何成为图灵完备的？它缺乏文件系统、适当的多线程API，由于其浏览器安全沙盒性质，它有很多限制。它几乎不能被称为“编程语言”。看看有多少种脚本抽象存在（React、TypeScript等），所有这些都是为了弥补JS所缺乏的东西。（在这里应该提到asm.js）。Java、Python或C++是真正的“图灵完备”例子。但JS呢？我不这么认为。 - Michael IV

@MichaelIV 这台巡回机器也没有文件系统/线程。JavaScript 绝对是图灵完备的。 - Bax

@MichaelIV 除了Bax的回答之外，我们还可以考虑把现代计算机看作是由多个图灵机共同协作来实现你提到的所有好处。例如，CPU生成“磁带”供GPU读取，以便它可以为显示器编写“磁带”，以便显示器可以向用户编写“磁带”。同样，CPU也可以为硬盘、网卡、声卡等设备生成“磁带”。 - user3003999

JS是绝对的图灵完备 - 但图灵完备性比你想象中的标准要低。这并不意味着它适用于任何计算。例如：一种语言不需要能够乘除数字来满足图灵完备性，只要它能够加法、循环和条件语句就行了。它之所以是图灵完备的，是因为你可以使用那些其他功能编写一个函数来完成乘法运算。 - Kyle Alm

Answer 3

非正式定义

图灵完备语言是指能够执行任何计算的语言。 “ Church-Turing Thesis ” 表明，任何可行的计算都可以通过图灵机来完成。 图灵机 是一种具有无限随机访问内存和有限程序的机器，该程序规定了它何时应读取、写入和在内存中移动，何时以特定结果终止以及接下来应该做什么。输入到图灵机中之前会被放在它的内存中。

可能使语言不是图灵完备的因素

图灵机可以基于其看到的内存内容做出决策 - 只支持对整数使用+,-,*和/的“语言”并非图灵完备，因为它不能根据输入进行选择，但图灵机可以。

图灵机可以永远运行 - 如果我们从Java、Javascript或Python中删除了任何形式的循环、GOTO或函数调用能力，它将不是图灵完备的，因为它不能执行任何永不结束的计算。Coq 是一个定理证明器，无法表达不终止的程序，因此它不是图灵完备的。

图灵机可以使用无限内存 - 如果有一种与Java完全相同的语言，但一旦使用超过4吉字节的内存就会终止，那么它将不是图灵完备的，因为图灵机可以使用无限内存。这也是正则表达式不是图灵完备的原因之一，而Java仍然是图灵完备的语言，因为Java 语言没有限制它使用无限内存的能力。

图灵机具有随机访问内存 - 如果一种语言只能通过对栈执行push和pop操作来处理内存，则该语言不是图灵完备的。如果我有一个“语言”，它只读取一次字符串，并且只能通过从栈中推入和弹出来使用内存，则可以通过在看到(时推入并在看到)时弹出来告诉我字符串中的每个(是否有自己的) 。然而，它无法告诉我每个(都有自己的)并且每个[都有自己的]（请注意，([)]符合此标准，但([]]不符合）。图灵机可以使用其随机访问内存分别跟踪()和[]，但是这种仅具有堆栈的语言无法做到。

图灵机可以模拟任何其他图灵机 - 给定适当的“程序”，图灵机可以接受另一个图灵机的“程序”并在任意输入上模拟它。如果您的语言禁止实现Python解释器，则它不是图灵完备的。

图灵完备语言示例

如果您的语言具有无限随机访问内存、条件执行和某种形式的重复执行，那么它可能是图灵完备的。还有一些更奇特的系统，它们仍然可以实现图灵机能做到的一切，这也使它们成为图灵完备系统：

• 未类型化的λ演算
• 康威生命游戏
• C++模板
• Prolog

- Gordon Gustafson

---

SQL绝对是图灵完备的。它具有脚本编程能力，可以进行任何计算。 - nzifnab

不，你把SQL和扩展（如T-SQL / PL-SQL）混淆了。ANSI SQL不是图灵完备的，但是T-SQL / PL-SQL是图灵完备的。 - Agnius Vasiliauskas

SQL 显然是图灵完备的：https://dev59.com/DXNA5IYBdhLWcg3wmfEa - Newtang

根据图灵完备性 - 如果系统可以用于模拟任何单带图灵机，则该系统是图灵完备的。但是在上面的例子中，据我所知，开发人员构建了特定的“循环标记系统”，而不是“通用循环标记系统”。因此 - 该文章并未证明SQL具有图灵完备性。（或者我误解了什么） - Agnius Vasiliauskas

没有可实现的图灵完备语言，因为不存在无限的纸带。实际上我们指的是，一些语言具有近似达到图灵完备性的能力，但受主机内存限制。 - Shelby Moore III

Answer 4

根据 维基百科:

图灵完备性(Turing completeness)是以艾伦·图灵的名字命名的，其重要性在于目前为止每个计算设备的可行设计都可以被通用图灵机所模拟 - 这一观察被称为“丘奇-图灵论题”。因此，一个能够作为通用 图灵机 的机器原则上可以执行任何其他可编程计算机能够执行的计算。然而，这与编写程序所需的工作量、机器执行计算所需的时间以及机器可能拥有的与计算无关的能力无关。

虽然真正的图灵完备机器很可能在物理上是不可能的，因为它们需要无限的存储空间，但图灵完备性通常被宽泛地归属于如果它们有无限存储空间就会成为通用的实际机器或编程语言。所有现代计算机在这个意义上都是图灵完备的。

除非说“图灵完备意味着‘在足够的时间和空间下能够回答可计算问题’”，否则我不知道你如何比这更非技术性地表达了。

- Ran Biron

---

在这个语境中，“computing device”指的是“计算设备”。 - dopatraman

大多数维基百科文章都是如此，虽然这个引用在技术上是正确的，但对于那些对该主题没有任何了解并试图理解它的人来说，它并没有提供任何价值。能够清晰地解释事物是一门学问 :) - LachoTomov

循环定义。"Turing-Complete"是指能够运行"通用图灵机"的东西。这就引出了一个问题：什么是"图灵机"......答案又不是很有帮助。 - coolaj86

Answer 5

图灵完备意味着它至少和一台图灵机一样强大。这意味着任何能够被图灵机计算的东西都可以被图灵完备系统计算。

目前还没有比图灵机更加强大的系统被发现，所以暂时来说，说一个系统是图灵完备的就等同于说这个系统和任何已知的计算系统一样强大 (详见Church-Turing Thesis)。

- Waylon Flinn

---

请注意，这一切都不考虑时间因素。它只是说“可以做到”。 - Thorbjørn Ravn Andersen

@ThorbjørnRavnAndersen 实际上，它完全忽略了物理可计算性。它不仅可能需要比宇宙年龄更长的时间，而且还可能使用超过宇宙中所有费米子和玻色子构造的内存。 - Waylon Flinn

宇宙中玻色子和费米子的数量可能是无限的，我们不知道也很可能永远不会知道它的大小。每当你读到有关“宇宙”中X的数量时，人们实际上是在谈论可观测宇宙。虽然这很有趣，但它并不是一个实际的物理限制。 - Stijn de Witt

通常人们认为“强大”的意思是“计算速度快”（这个概念可以与复杂性理论相提并论），如果图灵机能够完成任务（可计算性理论），那么它就是完备的。但由于措辞不准确或错误，这个答案可能会误导人。 - Soleil

Answer 6

从根本上讲，图灵完备性只有一个简明要求：无限递归。

甚至不受内存的限制。

我独立思考过这个问题，但是这里有一些关于这个说法的讨论。我的LSP定义提供了更多上下文信息。

这里的其他答案没有直接定义图灵完备性的基本本质。

- Shelby Moore III

---

有限状态自动机允许具有无限递归。例如：a*。 - user824425

FSM（有限状态机）的记忆能力是有限的（即状态数有限），但没有尾优化的无限递归需要无限制的内存。我并没有将我的定义限制在仅具有尾部优化的无限递归子集中。请取消你的投票反对。 - Shelby Moore III

你把无限递归的定义保持得模糊不清。你是指“递归”在“原始递归”的意义上，“无限”的含义是通过使其“部分”（或“一般”，或“mu-”）来实现的吗？那么你可能是对的。但是你目前的表述方式与David Harel的《关于民间定理》中批评的陈述非常接近。在数学上严谨很重要，而通过省略精确定义，你正在忽视这一点。顺便说一下：有限状态机可以推广到模拟交互；它们与图灵机的区别在于后者的环境也被建模（作为纸带）。 - user824425

@Rhymoid枚举是精度的反义词，例如列举英寸分数的最大精度。无限递归意味着每种可能的递归形式，这在没有无限纸带的情况下是不可能的。完全泛化递归（不仅仅是模型内部的一般化）总是图灵完备的。我在陈述泛化递归和执行任何可能计算的能力之间的等价性。这是一个重要的等价性需要注意。 - Shelby Moore III

"无限递归意味着每种可能的递归形式。" 这是你的理解。对于大多数SO用户来说，“无限递归”意味着 while (p) { /* ... */ }。 "我在阐述广义递归和执行任何可能计算的能力之间的等价性。" Church's thesis 是一个非常不同的问题，应该真正分开讨论。 - user824425

Answer 7

简单来说，图灵完备系统可以解决任何可能的计算问题。

其中一个关键要求是擦板大小无限制，并且可以倒回以访问先前写入的擦板。

因此，在实践中，没有任何系统是图灵完备的。

相反，一些系统通过模拟无限制内存并执行适合于系统内存的任何可能计算来近似于图灵完备性。

- Shelby Moore III

Answer 8

以下是自己在视频中总结的超简要点。

Turing Complete ≅ 可以做任何图灵机能做的事情。

1. 它具有条件分支（即“if语句”）。同时，意味着“跳转”，从而允许循环。

2. 它可以获得程序所需的任意数量的内存（例如足够长的磁带）。

- Glenn Mohammad

Answer 9

我认为“图灵完备”的重要性在于它能够识别一个计算机（不一定是机械/电子“计算机”），该计算机的过程可以被分解成“简单”的指令，由更简单的指令组成，一个通用机器可以解释并执行。

我强烈推荐《注释图灵》。

@马克，我认为你所解释的是通用图灵机和图灵完备之间的混合描述。

实际上，某些能够被编写和表示为程序并可由通用机（台式电脑）执行的机器/过程/计算机将是Turing Complete。虽然如其他人所提到的，它不考虑时间或存储。

- Brian Leahy

Answer 10

图灵机要求任何程序都能执行条件测试。这是基本的。

考虑一下自动钢琴卷轴。自动钢琴可以演奏高度复杂的音乐，但音乐中从来没有条件逻辑。它不是图灵完备的。

条件逻辑既是图灵完备机器的力量，也是危险所在。

钢琴卷轴保证每次都会停止。对于图灵机来说，没有这样的保证。这被称为“停机问题”。

- Richard Riehle