关于理论：什么是图灵完成？

What is Turing Complete?

"图灵完备"一词是什么意思？

你能在不涉及太多理论细节的情况下给出一个简单的解释吗？

下面是最简单的解释：

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

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

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

下面是最简单的解释

阿兰·图灵发明了一种机器，它可以接受一个程序并运行该程序并显示一些结果。但后来他不得不为不同的程序创建不同的机器。所以他创建了"通用图灵机"，可以接受任何程序并运行它。

编程语言类似于那些机器(尽管是虚拟的)。他们接受程序并运行它们。现在，一种编程语言被称为"图灵完成"，如果它能运行图灵机器在给定的时间和内存下可以运行的任何程序(不管语言如何)。

例如：假设有一个程序取10个数字并将其相加。图灵机可以很容易地运行这个程序。但是现在想象一下，由于某种原因，你的编程语言不能做同样的添加，那么图灵机器就不完整了。另一方面，如果它能运行任何程序，比如通用图灵机可以运行，那么它就完成了图灵机。

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

更新：你可以在我的博客上了解更多："javascript是图灵完成"？-？解释

维基百科：

Turing completeness, named after Alan
Turing, is significant in that every
plausible design for a computing
device so far advanced can be emulated
by a universal Turing machine — an
observation that has become known as
the Church-Turing thesis. Thus, a
machine that can act as a universal
Turing machine can, in principle,
perform any calculation that any other
programmable computer is capable of.
However, this has nothing to do with
the effort required to write a program
for the machine, the time it may take
for the machine to perform the
calculation, or any abilities the
machine may possess that are unrelated
to computation.

While truly Turing-complete machines
are very likely physically impossible,
as they require unlimited storage,
Turing completeness is often loosely
attributed to physical machines or
programming languages that would be
universal if they had unlimited
storage. All modern computers are
Turing-complete in this sense.

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

非正式定义

图灵完备语言是一种可以执行任何计算的语言。丘奇图灵理论指出，任何可执行的计算都可以由图灵机器完成。图灵机是一种具有无限随机存取存储器和有限"程序"的机器，它规定了它应该何时读、写和移动该存储器，何时应该以某个结果终止，以及接下来应该做什么。图灵机的输入在启动前就被放入内存中。

使语言不完整的事物

一个图灵机可以根据它在内存中看到的内容来做出决定——只支持+、-、*和/的"语言"在整数上不是图灵全的，因为它不能根据输入做出选择，但是图灵机可以。

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

图灵机可以使用无限内存——一种完全类似Java的语言，但是一旦使用超过4千兆字节的内存，它就不会终止，因为图灵机可以使用无限内存。这就是为什么我们不能真正构建一个图灵机，但是Java仍然是一个图灵完整的语言，因为Java语言没有限制它使用无限内存。这就是正则表达式不完整的原因之一。

图灵机具有随机存取存储器——一种只允许您通过push和pop操作对堆栈使用存储器的语言不会是图灵全的。如果我有一种"语言"，它只读一次字符串，只能通过从堆栈中推和弹出来使用内存，它可以告诉我，字符串中的每个(以后是否都有自己的)，当它看到(时推，当它看到)时弹出。但是，它不能告诉我，以后每个(是否都有自己的)，以后每个[是否都有自己的](注意，([)]是否符合这一标准，但([]]不符合)。图灵机可以使用其随机存取存储器分别跟踪()和[]，但这种只有堆栈的语言不能。