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!)

图灵等价比真正的图灵完备性更主流;这一点以及“完全”比“等效”短的事实可能解释了为什么“图灵完全”经常被误用为图灵等效，但我离题了。

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

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

这是最简单的解释

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

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

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

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

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

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!)

图灵等价比真正的图灵完备性更主流;这一点以及“完全”比“等效”短的事实可能解释了为什么“图灵完全”经常被误用为图灵等效，但我离题了。

非正式的定义

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

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

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

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

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

A Turing machine has random access memory - A language that only lets you work with memory through push and pop operations 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.

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

图灵完备语言的例子

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

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

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

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

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

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