什么是图灵完备?

从# EYZ0:

图灵完备性，以图灵命名 图灵在每一个方面都很重要 计算的合理设计 如此先进的设备是可以模仿的 一个通用图灵机 观察被称为 丘奇-图灵的论文。因此,一个 可以充当通用机器的机器 原则上图灵机可以， 执行任何其他计算 可编程计算机的能力。 然而，这无关紧要 编写程序所需要的努力 对于机器来说，可能需要的时间 为机器执行 计算，或任何能力 机器可能拥有不相关的东西 计算。< / p > 而真正的图灵完备机 在物理上是不可能的 因为它们需要无限的存储空间， 图灵完备性通常是松散的 归因于物理机器或 编程语言就是这样 如果他们有无限，那就是万能的 存储。所有现代计算机都是

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

以下是最简单的解释:

图灵完备系统指的是这样一个系统，在这个系统中，可以编写程序来找到答案(尽管不保证运行时间或内存)。

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

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

我认为“图灵完备”概念的重要性在于能够识别一台计算机(不一定是机械/电气“计算机”)，它可以将其过程分解为由越来越简单的指令组成的“简单”指令，通用机可以解释并执行这些指令。

我强烈推荐《注释图灵》

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

从实际意义上讲，图灵完备指的是一台机器/过程/计算，它可以被编写并表示为程序，由通用机(台式计算机)执行。虽然它不考虑时间或存储，正如其他人所提到的。

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

目前还没有人发现比图灵机更强大的系统。因此，就目前而言，说一个系统是图灵完备的，就等于说这个系统与任何已知的计算系统一样强大(参见Church-Turing论文)。

# EYZ0:

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

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

非正式的定义

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

可以使一种语言不是图灵完备的东西

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

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

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

pop4——一种只允许你通过push和pop对堆栈操作来处理内存的语言不是图灵完备的。如果我有一种“语言”，读取字符串pop5，只能通过从堆栈中推和弹出来使用内存，它可以告诉我是否字符串中的每个(都有自己的)，当它看到(时推，当它看到)时弹出。然而，它不能告诉我是否每个(都有自己的)，然后pop6，每个[都有自己的](注意，pop0符合这个标准，但pop1不符合)。图灵机可以使用随机存取存储器分别跟踪pop2和pop3，但是这种只有堆栈的语言不能。

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

图灵完备语言的例子

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

• 无类型lambda演算
• 康威的人生游戏
• c++模板
• 序言

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

甚至不受记忆的限制。

我是独立思考的，但是下面是一些讨论的断言。我对LSP的定义提供了更多的上下文。

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

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

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

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

关键要求之一是便签大小不受限制，并且可以倒带访问之前对便签的写操作。

因此在实践中没有一个系统是图灵完备的。

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

这是最简单的解释

艾伦·图灵创造了一台机器，它可以接收程序，运行程序，并显示结果。但是他必须为不同的程序创造不同的机器。于是他创造了“通用图灵机”;可以获取任何程序并运行它。

编程语言类似于这些机器(尽管是虚拟的)。他们获取程序并运行它们。现在，一种编程语言被称为“图灵完整”，如果它可以运行图灵机在足够的时间和内存下可以运行的任何程序(无论哪种语言)。

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

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

更新:你可以在我的博客文章“JavaScript是图灵完整的”-解释上了解更多

在大多数程序员熟悉的实际语言术语中，检测图灵完整性的通常方法是该语言是否允许或允许模拟嵌套的无界while语句(与具有固定上界的pascal风格for语句相反)。

考虑一个播放器钢琴卷。钢琴播放器可以 演奏一段非常复杂的音乐， 但是从来没有任何条件逻辑 音乐。它是不图灵完成

条件逻辑既是权力，也是权力

Brasilford教授在这个视频中解释的超级简短的总结。

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

1. 它有条件分支(即“if语句”)。同样，暗示着“去”;因此允许循环。

2. 它得到程序所需的任意数量的内存(例如足够长的磁带)。

我们称一种语言为图灵完备当且仅当(1)它可以被图灵机决定，但(2)不能被任何能力低于图灵机的东西决定。例如，字母{a, b}上的回文语言可以由图灵机决定，但也可以由下推自动机决定;所以，这种语言不是图灵完备的。真正的图灵完备语言——需要图灵机全部计算能力的语言——是相当罕见的。也许是字符串语言x.y.z，其中x是数字，y是图灵机，z是初始磁带配置，y在小于x的时间内停在z上!步骤-也许这是合格的(尽管它需要显示!)

一种常见的不精确用法混淆了图灵完备性和图灵等价性。图灵等价是指计算系统可以模拟图灵机，也可以被图灵机模拟的特性。例如，我们可以说Java是一种与图灵机等效的编程语言，因为可以用Java编写图灵机模拟器，并且可以定义模拟Java程序执行的图灵机。根据丘奇-图灵命题，图灵机可以执行任何有效的计算，所以图灵等价意味着一个系统是尽可能有能力的(如果丘奇-图灵命题是正确的!)

图灵等价比真正的图灵完备性更主流;事实上，“完整”;比“等价”短;也许可以解释为什么“图灵完全”;常被误用为图灵等价，但我跑题了。