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

非正式的定义

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

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

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

图灵机可以永远运行——如果我们使用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++模板 序言

图灵机要求任何程序 能进行条件测试。这是最基本的。

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

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

钢琴的滚动每次都保证会停止。 对于TM来说，没有这样的保证。这 被称为“停止问题”。

从维基百科:

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.

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

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

这是最简单的解释

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

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

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

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

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