非正式的定义

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

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

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

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

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

我强烈推荐《注释图灵》

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

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

以下是最简单的解释:

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

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

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

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

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

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

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

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

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

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

甚至不受记忆的限制。

我是独立思考的，但这里有一些关于这个论断的讨论。我对LSP的定义提供了更多的上下文。

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