什么是图灵完备性？

Question

什么是图灵完备性？

language-agnostictheoryturing-machinesturing-complete

699

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

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

- dlinsin

6

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

2

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

14个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Keith Douglas · Answer 1

在大多数程序员熟悉的实际语言术语中，检测图灵完备性的常规方法是检查该语言是否允许或模拟嵌套无限制 while 语句（而不是带有固定上限的 Pascal 风格 for 语句）。

- ChrisC · Answer 2

-2

正如Waylon Flinn所说：

Turing完备意味着它至少与图灵机一样强大。

我认为这是不正确的，一个系统只有在与图灵机完全相等时才是Turing完备的，即机器执行的每个计算都可以由该系统执行，但该系统执行的每个计算也可以由图灵机执行。

- ChrisC

2

我认为你假设了 Church-Turing 论题是正确的，才得出这个结论。但它尚未被证明。你所描述的属性被称为“图灵等价”。 - Waylon Flinn

2

@WaylonFlinn 不，他是对的。 "完备性" 既意味着它至少和一件事情一样强大，但也不会更强。与 "NP-完全" 相比较。 - Devin Jeanpierre

4

@DevinJeanpierre，我不想在这里引发争端，但我几乎可以确定你所描述的计算类别称为“图灵等价”。虽然“图灵完备”确实与NP完全问题有相似之处。如果P=NP，则NP完全等于NP。同样，如果且仅当Church-Turing假设正确时，“图灵完备”等于“图灵等价”。 - Waylon Flinn

6

在你提供的维基百科文章中，它明确写道。引用正式定义部分：“能够计算每个图灵可计算函数的计算系统被称为图灵完备”，“如果一个图灵完备系统可以计算的每个函数也都是图灵可计算的，则该系统被称为图灵等效”。 - Waylon Flinn

@WaylonFlinn 你曾写道：“如果且仅如果Church-Turing论题正确，那么图灵完备等同于图灵等效。”但是，图灵等效不是一个更广泛的概念吗？两个系统可以相互图灵等效，尽管它们只能执行图灵机的子集计算。因此，图灵完备性是相对于通用图灵机的图灵等效性。 - Ataxias

显示剩余2条评论

- Patrick87 · Answer 3

如果一种语言是可由图灵机决定的，但不可由比图灵机更低级别的任何东西决定，则我们称其为图灵完备。例如，字母表{a，b}上的回文语言可以由图灵机和下推自动机决定；因此，这种语言不是图灵完备的。真正的图灵完备语言——需要图灵机的全部计算能力——非常罕见。也许字符串x.y.z的语言就是一个例子，其中x是一个数字，y是一个图灵机，z是一个初始磁带配置，并且y在少于x！步骤中停止——也许这就符合条件（尽管需要证明！）

常见的不精确用法将图灵完备性与图灵等效性混淆。图灵等效性指的是一种计算系统的属性，该系统可以模拟图灵机，并且可以被图灵机模拟。例如，我们可以说Java是一种图灵等效的编程语言，因为您可以在Java中编写图灵机模拟器，并且可以定义一个模拟执行Java程序的图灵机。根据Church-Turing论题，图灵机可以执行任何有效的计算，因此图灵等效性意味着系统具有最大的能力（如果Church-Turing论题成立的话！）

图灵等价是一个更为主流的问题，而不仅仅是真正的图灵完备性；这一点以及“complete”比“equivalent”更短可能解释了为什么“Turing-complete”经常被错误地用来表示图灵等价，但我岔开了话题。

- Akshay Jain · Answer 4

关系型数据库能够输入地点和道路的经纬度，并计算它们之间的最短路径吗？答案是否定的。这是一个表明SQL并非图灵完备的问题。

但是C++可以做到，而且可以解决任何问题。因此它是优秀的选择。