什么是图灵完备？
“图灵完备”这个表达是什么意思？
您能否给出一个简单的解释，而不涉及太多理论细节？
What does the expression "Turing Complete" mean?
Can you give a simple explanation, without going into too many theoretical details?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（14）
这是最简短的解释：
图灵完备系统意味着可以在其中编写可以找到答案的程序的系统（尽管不能保证运行时或内存）。
因此，如果有人说“我的新东西是图灵完备”，这意味着原则上（尽管在实践中通常不是）它可以用来解决任何计算问题。
有时这是一个笑话......一个人用 vi 编写了图灵机模拟器，因此可以说 vi 是世界上唯一需要的计算引擎。
Here's the briefest explanation:
A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory).
So, if somebody says "my new thing is Turing Complete" that means in principle (although often not in practice) it could be used to solve any computation problem.
Sometimes it's a joke... a guy wrote a Turing Machine simulator in vi, so it's possible to say that vi is the only computational engine ever needed in the world.
这是最简单的解释
艾伦图灵创建了一台可以接受程序、运行该程序并显示一些结果的机器。 但随后他必须为不同的程序创建不同的机器。 所以他创造了“通用图灵机”，可以接受任何程序并运行它。
编程语言与那些机器类似（尽管是虚拟的）。 他们获取程序并运行它们。 现在，如果一种编程语言可以运行图灵机在给定足够时间和内存的情况下可以运行的任何程序（无论哪种语言），则该编程语言被称为“图灵完备”。
例如：假设有一个程序需要 10 个数字并将它们相加。 图灵机可以轻松运行该程序。 但现在想象一下，由于某种原因，您的编程语言无法执行相同的加法。 这将使其成为“图灵不完备”（可以这么说）。 另一方面，如果它可以运行通用图灵机可以运行的任何程序，那么它就是图灵完备的。
大多数现代编程语言（例如 Java、JavaScript、Perl 等）都是图灵完备的，因为它们各自实现了运行程序所需的所有功能，例如加法、乘法、if-else 条件、返回语句、存储/检索/擦除的方法数据等。
更新：您可以在我的博客文章中了解更多信息： "JavaScript图灵完备吗”——解释
Here is the simplest explanation
Alan Turing created a machine that can take a program, run that program, and show some result. But then he had to create different machines for different programs. So he created "Universal Turing Machine" that can take ANY program and run it.
Programming languages are similar to those machines (although virtual). They take programs and run them. Now, a programing language is called "Turing complete", if it can run any program (irrespective of the language) that a Turing machine can run given enough time and memory.
For example: Let's say there is a program that takes 10 numbers and adds them. A Turing machine can easily run this program. But now imagine that for some reason your programming language can't perform the same addition. This would make it "Turing incomplete" (so to speak). On the other hand, if it can run any program that the universal Turing machine can run, then it's Turing complete.
Most modern programming languages (e.g. Java, JavaScript, Perl, etc.) are all Turing complete because they each implement all the features required to run programs like addition, multiplication, if-else condition, return statements, ways to store/retrieve/erase data and so on.
Update: You can learn more on my blog post: "JavaScript Is Turing Complete" — Explained
非正式定义
图灵完备的语言是一种可以执行任何计算的语言。 Church-Turing Thesis 指出任何可执行的计算都可以通过图灵机。 图灵机是一台具有无限随机存取存储器和有限“程序”的机器，该程序决定何时运行应该读取、写入和移动该内存，何时应以某个结果终止，以及下一步应该做什么。 图灵机的输入在启动之前被放入其内存中。
可以使语言不图灵完整的东西
图灵机可以根据它在内存中看到的内容做出决策 - 仅支持
+，-的“语言”整数上的、*和/不是图灵完备的，因为它无法根据输入做出选择，但图灵机可以。图灵机可以永远运行 - 如果我们采用 Java、Javascript 或 Python 并删除执行任何类型的循环、GOTO 或函数调用的能力，它就不是图灵完备的，因为它可以不要执行永远不会完成的任意计算。 Coq 是一个定理证明器，无法表达不会终止的程序，因此它不是图灵完全的。
图灵机可以使用无限内存 - 一种与 Java 完全相同但一旦使用超过 4 GB 内存就会终止的语言不是图灵完备的，因为图灵机可以使用无限内存。 这就是为什么我们实际上无法构建图灵机，但 Java 仍然是图灵完备的语言，因为 Java 语言没有限制它使用无限内存。 这是正则表达式不是图灵完备的原因之一。
图灵机具有随机存取存储器 - 一种仅允许您通过对堆栈进行
push和pop操作来使用内存的语言不会是图灵完成。 如果我有一种“语言”可以读取字符串一次并且只能通过从堆栈中压入和弹出来使用内存，那么它可以告诉我字符串中的每个(是否有稍后，当它看到(时推送，并在看到)时弹出。 但是，它无法告诉我是否每个(都有自己的)稍后和每个[都有自己的)稍后拥有]（请注意，([)]满足此条件，但([]]不满足)。图灵机可以使用其随机存取存储器可以分别跟踪()和[]，但是这种只有堆栈的语言不能图灵机可以模拟任何其他图灵机 。机器 - 当给定适当的“程序”时，图灵机可以采用另一台图灵机的“程序”并在任意输入上模拟它如果您有一种被禁止实现Python解释器的语言，它就不会。 如果您的语言具有无限随机存取存储器、条件执行和某种形式的重复执行，那么它可能是
图灵完备语言的示例
图灵完备的。还有更多奇特的系统仍然可以实现图灵机所能实现的一切。也使它们图灵完备：
Informal Definition
A Turing complete language is one that can perform any computation. The Church-Turing Thesis states that any performable computation can be done by a Turing machine. A Turing machine is a machine with infinite random access memory and a finite 'program' that dictates when it should read, write, and move across that memory, when it should terminate with a certain result, and what it should do next. The input to a Turing machine is put in its memory before it starts.
Things that can make a language NOT Turing complete
A Turing machine can make decisions based on what it sees in memory - The 'language' that only supports
+,-,*, and/on integers is not Turing complete because it can't make a choice based on its input, but a Turing machine can.A Turing machine can run forever - If we took Java, Javascript, or Python and removed the ability to do any sort of loop, GOTO, or function call, it wouldn't be Turing complete because it can't perform an arbitrary computation that never finishes. Coq is a theorem prover that can't express programs that don't terminate, so it's not Turing complete.
A Turing machine can use infinite memory - A language that was exactly like Java but would terminate once it used more than 4 Gigabytes of memory wouldn't be Turing complete, because a Turing machine can use infinite memory. This is why we can't actually build a Turing machine, but Java is still a Turing complete language because the Java language has no restriction preventing it from using infinite memory. This is one reason regular expressions aren't Turing complete.
A Turing machine has random access memory - A language that only lets you work with memory through
pushandpopoperations to a stack wouldn't be Turing complete. If I have a 'language' that reads a string once and can only use memory by pushing and popping from a stack, it can tell me whether every(in the string has its own)later on by pushing when it sees(and popping when it sees). However, it can't tell me if every(has its own)later on and every[has its own]later on (note that([)]meets this criteria but([]]does not). A Turing machine can use its random access memory to track()'s and[]'s separately, but this language with only a stack cannot.A Turing machine can simulate any other Turing machine - A Turing machine, when given an appropriate 'program', can take another Turing machine's 'program' and simulate it on arbitrary input. If you had a language that was forbidden from implementing a Python interpreter, it wouldn't be Turing complete.
Examples of Turing complete languages
If your language has infinite random access memory, conditional execution, and some form of repeated execution, it's probably Turing complete. There are more exotic systems that can still achieve everything a Turing machine can, which makes them Turing complete too:
来自维基百科：
我不知道你怎么能比这更非技术性，除了说“图灵完备意味着‘在给定足够的时间和空间的情况下能够回答可计算的问题’”。
From wikipedia:
I don't know how you can be more non-technical than that except by saying "turing complete means 'able to answer computable problem given enough time and space'".
我认为“图灵完备”概念的重要性在于能够识别计算机（不一定是机械/电气“计算机”），可以将其过程解构为“简单”指令，由越来越简单的指令组成通用机器可以解释然后执行的指令。
我强烈推荐注释图灵
@Mark，我认为你所解释的是通用图灵机和图灵完整的描述之间的混合。
从实际意义上来说，图灵完备的东西将是能够被编写并表示为程序、由通用机（台式计算机）执行的机器/过程/计算。 尽管正如其他人提到的，它没有考虑时间或存储。
I think the importance of the concept "Turing Complete" is in the the ability to identify a computing machine (not necessarily a mechanical/electrical "computer") that can have its processes be deconstructed into "simple" instructions, composed of simpler and simpler instructions, that a Universal machine could interpret and then execute.
I highly recommend The Annotated Turing
@Mark i think what you are explaining is a mix between the description of the Universal Turing Machine and Turing Complete.
Something that is Turing Complete, in a practical sense, would be a machine/process/computation able to be written and represented as a program, to be executed by a Universal Machine (a desktop computer). Though it doesn't take consideration for time or storage, as mentioned by others.
从根本上来说，图灵完备性是一种简洁的要求，无界递归。
甚至不受记忆的限制。
我独立地想到了这一点，但是这里是对该断言的一些讨论。 我对 LSP 的定义提供了更多上下文。
这里的其他答案并没有直接定义图灵完备性的基本本质。
Fundamentally, Turing-completeness is one concise requirement, unbounded recursion.
Not even bounded by memory.
I thought of this independently, but here is some discussion of the assertion. My definition of LSP provides more context.
The other answers here don't directly define the fundamental essence of Turing-completeness.
图灵完备意味着它至少与图灵机一样强大。 这意味着任何可以由图灵机计算的东西都可以由图灵完备系统计算。
还没有人发现比图灵机更强大的系统。 因此，就目前而言，说一个系统是图灵完备的就等于说该系统与任何已知的计算系统一样强大（参见教会图灵论文）。
Turing Complete means that it is at least as powerful as a Turing Machine. This means anything that can be computed by a Turing Machine can be computed by a Turing Complete system.
No one has yet found a system more powerful than a Turing Machine. So, for the time being, saying a system is Turing Complete is the same as saying the system is as powerful as any known computing system (see Church-Turing Thesis).
用最简单的术语来说，图灵完备的系统可以解决任何可能的计算问题。
关键要求之一是暂存器大小不受限制，并且可以倒带以访问先前对暂存器的写入。
因此，实际上没有系统是图灵完备的。
相反，一些系统通过对无界内存进行建模并执行适合系统内存的任何可能的计算来近似图灵完备性。
In the simplest terms, a Turing-complete system can solve any possible computational problem.
One of the key requirements is the scratchpad size be unbounded and that is possible to rewind to access prior writes to the scratchpad.
Thus in practice no system is Turing-complete.
Rather some systems approximate Turing-completeness by modeling unbounded memory and performing any possible computation that can fit within the system's memory.
Brasilford 教授在此视频中解释的内容的超级简短摘要。
图灵完备 ≅ 做图灵机能做的任何事情。
它具有条件分支（即“if 语句”）。 此外，还意味着“转到”，从而允许循环。
它获得程序需要的任意数量的内存（例如足够长的磁带）。
Super-brief summary from what Professor Brasilford explains in this video.
Turing Complete ≅ do anything that a Turing Machine can do.
It has conditional branching (i.e. "if statement"). Also, implies "go to" and thus permitting loop.
It gets arbitrary amount of memory (e.g. long enough tape) that the program needs.
我们称一种语言是图灵完备的，当且仅当（1）它可以由图灵机判定，但（2）不能由任何能力低于图灵机的东西判定。 例如，字母表 {a, b} 上的回文语言可以由图灵机判定，但也可以由下推自动机判定； 所以，这种语言不是图灵完备的。 真正的图灵完备语言——需要图灵机的全部计算能力的语言——非常罕见。 也许是字符串 xyz 的语言，其中 x 是数字，y 是图灵机，z 是初始磁带配置，并且 y 在 z 上停止的时间少于 x！ 步骤 - 也许这符合条件（尽管需要显示！）
一种常见的不精确用法将图灵完备性与图灵等价性混淆了。 图灵等价是指可以模拟图灵机并且可以由图灵机模拟的计算系统的属性。 例如，我们可能会说 Java 是一种与图灵机等效的编程语言，因为您可以用 Java 编写图灵机模拟器，并且因为您可以定义一个模拟 Java 程序执行的图灵机。 根据丘奇-图灵理论，图灵机可以执行任何有效的计算，因此图灵等价意味着系统尽可能有能力（如果丘奇-图灵理论是正确的！）
图灵等价是比真正的图灵更主流的关注点完整性； 这个以及“完整”比“等效”短的事实可以解释为什么“图灵完备”经常被误用为图灵等效，但我离题了。
We call a language Turing-complete if and only if (1) it is decidable by a Turing machine but (2) not by anything less capable than a Turing machine. For instance, the language of palindromes over the alphabet {a, b} is decidable by Turing machines, but also by pushdown automata; so, this language is not Turing-complete. Truly Turing-complete languages - ones that require the full computing power of Turing machines - are pretty rare. Perhaps the language of strings x.y.z where x is a number, y is a Turing-machine and z is an initial tape configuration, and y halts on z in fewer than x! steps - perhaps that qualifies (though it would need to be shown!)
A common imprecise usage confuses Turing-completeness with Turing-equivalence. Turing-equivalence refers to the property of a computational system which can simulate, and which can be simulated by, Turing machines. We might say Java is a Turing-equivalent programming language, for instance, because you can write a Turing-machine simulator in Java, and because you could define a Turing machine that simulates execution of Java programs. According to the Church-Turing thesis, Turing machines can perform any effective computation, so Turing-equivalence means a system is as capable as possible (if the Church-Turing thesis is true!)
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.
在大多数程序员熟悉的实用语言术语中，检测图灵完整性的常用方法是该语言是否允许或允许模拟嵌套无界 while 语句（与 Pascal 风格的 for 语句相反，具有固定的上限）。
In practical language terms familiar to most programmers, the usual way to detect Turing completeness is if the language allows or allows the simulation of nested unbounded while statements (as opposed to Pascal-style for statements, with fixed upper bounds).
正如 Waylon Flinn 所说：
我认为这是不正确的，如果一个系统与图灵机一样强大，那么它就是图灵完备的，即机器完成的每个计算都可以由系统完成，而且系统完成的每个计算也可以由图灵机完成。
As Waylon Flinn said:
I believe this is incorrect, a system is Turing complete if it's exactly as powerful as the Turing Machine, i.e. every computation done by the machine can be done by the system, but also every computation done by the system can be done by the Turing machine.
图灵机要求任何程序
可以进行条件测试。 这是根本性的。
考虑一下自动演奏的钢琴卷轴。 自动演奏钢琴可以
演奏一首高度复杂的音乐，
但其中从来不存在任何条件逻辑
音乐。 它不是图灵完备。
条件逻辑既是力量也是力量
图灵完备机器的危险。
保证钢琴卷帘每次都会停止。
TM 则不提供此类保证。 这
称为“停机问题”。
A Turing Machine requires that any program
can perform condition testing. That is fundamental.
Consider a player piano roll. The player piano can
play a highly complicated piece of music,
but there is never any conditional logic in the
music. It is not Turing Complete.
Conditional logic is both the power and the
danger of a machine that is Turing Complete.
The piano roll is guaranteed to halt every time.
There is no such guarantee for a TM. This
is called the “halting problem.”
关系数据库可以输入地点和道路的纬度和经度，并计算它们之间的最短路径吗？不能。 这是一个表明 SQL 不是图灵完备的问题。
但C++可以做到，并且可以解决任何问题。 确实如此。
Can a relational database input latitudes and longitudes of places and roads, and compute the shortest path between them - no. This is one problem that shows SQL is not Turing complete.
But C++ can do it, and can do any problem. Thus it is.