629

“图灵完备”的表达是什么意思？

你能给出一个简单的解释，而不涉及太多的理论细节吗？

4

14 回答 14

454

这是最简短的解释：

图灵完备系统是指可以编写程序并找到答案的系统（尽管不保证运行时或内存）。

所以，如果有人说“我的新东西是图灵完备”，这意味着原则上（尽管通常不是在实践中）它可以用来解决任何计算问题。

有时这是个笑话……一个人用 vi 写了一个图灵机模拟器，所以可以说 vi 是世界上唯一需要的计算引擎。

于 2008-08-10T20:10:48.687 回答
277

这是最简单的解释

Alan Turing 创造了一台可以接收程序、运行该程序并显示一些结果的机器。但随后他不得不为不同的程序创建不同的机器。所以他创造了“通用图灵机”，它可以接受任何程序并运行它。

编程语言类似于那些机器（尽管是虚拟的）。他们接受程序并运行它们。现在，一种编程语言被称为“图灵完备”，如果它可以运行图灵机在足够的时间和内存下可以运行的任何程序（与语言无关）。

例如：假设有一个程序需要 10 个数字并将它们相加。图灵机可以很容易地运行这个程序。但是现在想象一下，由于某种原因，您的编程语言无法执行相同的加法。这将使其“图灵不完整”（可以这么说）。另一方面，如果它可以运行通用图灵机可以运行的任何程序，那么它就是图灵完备的。

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

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

于 2016-05-16T05:17:26.823 回答
123

非正式定义

图灵完备的语言是一种可以执行任何计算的语言。Church-Turing Thesis指出，任何可执行的计算都可以由图灵机完成。图灵机是一台具有无限随机存取存储器和有限“程序”的机器，该程序指示它应该何时读取、写入和在该内存中移动，何时应该以特定结果终止，以及下一步应该做什么。图灵机的输入在它启动之前被放入它的内存中。

可以使语言不是图灵完整的事情

图灵机可以根据它在内存中看到的内容做出决定——仅支持+、-、*和/整数的“语言”不是图灵完备的，因为它无法根据输入做出选择，但图灵机可以。

图灵机可以永远运行——如果我们使用 Java、Javascript 或 Python 并删除执行任何类型的循环、GOTO 或函数调用的能力，它就不是图灵完整的，因为它不能执行任意计算永远不会结束。Coq是一个定理证明器，它不能表达不终止的程序，所以它不是图灵完备的。

图灵机可以使用无限内存- 一种与 Java 完全相同但一旦使用超过 4 GB 内存就会终止的语言不会是图灵完整的，因为图灵机可以使用无限内存。这就是为什么我们实际上无法构建图灵机，但 Java 仍然是图灵完备的语言，因为 Java语言没有限制它使用无限内存。这是正则表达式不是图灵完备的原因之一。

图灵机具有随机存取内存——一种只允许您通过内存push和pop对堆栈进行操作的语言不会是图灵完备的。如果我有一种“语言”，它读取一个字符串一次并且只能通过从堆栈中推送和弹出来使用内存，它可以告诉我(字符串中的每个人以后是否都有自己的内容，方法是在看到时)推送并在看到(时弹出)。但是，它不能告诉我以后是否每个(人都有自己的，)以后每个人都有自己的（请注意，符合此标准但不符合）。图灵机可以使用它的随机存取存储器来跟踪' 和[]([)]([]]()[]是分开的，但是这种只有堆栈的语言不能。

图灵机可以模拟任何其他图灵机-当给定适当的“程序”时，图灵机可以采用另一台图灵机的“程序”并在任意输入上对其进行模拟。如果你有一种被禁止实现 Python 解释器的语言，那它就不是图灵完备的。

图灵完备语言示例

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

  • 无类型 lambda 演算
  • 康威的人生游戏
  • C++ 模板
  • 序言
于 2009-10-22T23:45:42.453 回答
86

来自维基百科：

以艾伦·图灵命名的图灵完备性具有重要意义，因为迄今为止先进的计算设备的每一个合理设计都可以由通用图灵机模拟——这一观察已被称为 Church-Turing 论点。因此，可以作为通用图灵机的机器原则上可以执行任何其他可编程计算机能够执行的任何计算。然而，这与为机器编写程序所需的努力、机器执行计算所需的时间或机器可能拥有的与计算无关的任何能力无关。

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

我不知道你怎么能比这更非技术性，除了说“图灵完整意味着'能够在足够的时间和空间下回答可计算的问题'”。

于 2008-08-10T18:59:06.460 回答
18

从根本上说，图灵完备性是一个简洁的要求，即无限递归。

甚至不受记忆的限制。

我独立地想到了这一点，但这里是对断言的一些讨论。我对 LSP 的定义提供了更多的上下文。

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

于 2011-11-27T04:03:15.853 回答
16

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

还没有人找到比图灵机更强大的系统。所以，就目前而言，说一个系统是图灵完备的就等于说这个系统和任何已知的计算系统一样强大（参见Church-Turing Thesis）。

于 2009-05-18T17:09:11.900 回答
10

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

关键要求之一是暂存器大小不受限制，并且可以回退以访问对暂存器的先前写入。

因此实际上没有系统是图灵完备的。

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

于 2014-08-08T22:50:53.040 回答
3

我认为“图灵完备”概念的重要性在于识别计算机（不一定是机械/电气“计算机”）的能力，该计算机可以将其过程解构为“简单”指令，由越来越简单的指令组成指令，通用机器可以解释然后执行。

我强烈推荐带注释的图灵

@Mark我认为您要解释的是通用图灵机和图灵完备的描述之间的混合。

从实际意义上讲，图灵完备的东西是一种机器/过程/计算，可以编写和表示为程序，由通用机器（台式计算机）执行。尽管正如其他人所提到的，它没有考虑时间或存储。

于 2008-08-20T07:23:29.867 回答
2

来自 Brasilford 教授在此视频中解释的超级简短摘要。

图灵完备 ≅ 做图灵机能做的任何事情。

  1. 它有条件分支（即“if 语句”）。此外，暗示“去”，从而允许循环。

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

于 2021-02-18T13:08:15.720 回答
0

我们称一种语言为图灵完备的当且仅当 (1) 它可由图灵机判定，但 (2) 不能由比图灵机能力差的任何事物判定。例如，字母表 {a, b} 上的回文语言可由图灵机判定，但也可由下推自动机判定；所以，这种语言不是图灵完备的。真正图灵完备的语言——需要图灵机的全部计算能力的语言——非常罕见。也许是字符串 xyz 的语言，其中 x 是数字，y 是图灵机，z 是初始磁带配置，并且 y 在不到 x 的时间内停止在 z 上！步骤 - 也许符合条件（尽管需要显示！）

一个常见的不精确用法混淆了图灵完备性和图灵等效性。图灵等价性是指计算系统可以模拟并且可以由图灵机模拟的属性。例如，我们可以说 Java 是一种图灵等效的编程语言，因为您可以用 Java 编写图灵机模拟器，并且因为您可以定义一个图灵机来模拟 Java 程序的执行。根据 Church-Turing 论文，图灵机可以执行任何有效的计算，因此 Turing 等价意味着系统尽可能有能力（如果 Church-Turing 论文是真的！）

Turing equivalence is a much more mainstream concern that true Turing completeness; this and the fact that "complete" is shorter than "equivalent" may explain why "Turing-complete" is so often misused to mean Turing-equivalent, but I digress.

于 2021-04-10T17:47:05.353 回答
-1

在大多数程序员熟悉的实用语言术语中，检测图灵完整性的常用方法是该语言是否允许或允许模拟嵌套的无界 while 语句（与具有固定上限的 Pascal 式语句相反）。

于 2016-10-26T20:12:17.857 回答
-1

图灵机要求任何程序都可以执行条件测试。这是根本。

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

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

保证钢琴卷帘每次都停止。TM 没有这样的保证。这被称为“停机问题”。</p>

于 2020-03-18T20:18:20.763 回答
-2

正如韦伦弗林所说：

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

我认为这是不正确的，如果一个系统与图灵机一样强大，那么它就是图灵完备的，即机器完成的每个计算都可以由系统完成，而且系统完成的每个计算也可以由图灵机完成.

于 2009-10-05T23:18:19.903 回答
-9

关系数据库是否可以输入地点和道路的纬度和经度，并计算它们之间的最短路径 - 不。这是一个表明 SQL 不是图灵完备的问题。

但是 C++ 可以做到，并且可以解决任何问题。就是这样。

于 2012-12-15T18:33:53.127 回答