什么是图灵完成？
“Turing Complete”是什么意思？
你可以给一个简单的解释，而不会涉及太多的理论细节？
这是最简单的解释：
图灵完整系统意味着一个系统，在这个系统中可以编写一个程序来find答案（尽pipe没有关于运行时间或内存的保证）。
所以，如果有人说“我的新东西是图灵完全”，这意味着原则上（虽然经常不实际），它可以用来解决任何计算问题。
有时候这是一个笑话……一个人在vi编写了一个图灵机模拟器，所以有可能说vi是世界上唯一需要的计算引擎。
从维基百科 ：
以Alan Turing命名的图灵完备性是非常重要的，因为到目前为止，先进计算设备的每个合理devise都可以通过一个通用的图灵机来模拟 – 这个观察被称为教会 – 图灵论。 因此，可以充当通用图灵机的机器原则上可以执行任何其他可编程计算机能够进行的任何计算。 但是，这与编写机器程序所需的工作量，机器执行计算所需的时间或机器可能具有的与计算无关的任何能力无关。
虽然真正的图灵完整机器很可能在物理上是不可能的，因为它们需要无限存储，但图灵的完整性往往是松散地归因于物理机器或编程语言，如果它们具有无限的存储空间将是通用的。 所有现代计算机在这个意义上都是图灵完备的。
我不知道你怎么可能比这个更没有技术含义，除非说“能够在足够的时间和空间下解决可计算的问题”。
这是最简单的解释
Alan Turing创build了一个可以执行程序并运行该程序并显示一些结果的机器。 但是之后他必须为不同的程序创build不同的机器。 于是他创build了“通用图灵机”，可以采取任何程序并运行。
编程语言与这些机器类似（尽pipe是虚拟的）。 他们采取计划，并运行它们。 现在，一个编程语言被称为“图灵完成”，如果它可以运行任何程序（无论语言），一个图灵机可以运行足够的时间和记忆。
例如：假设有一个程序需要10个数字并添加它们。 图灵机可以很容易的运行这个程序。 但是现在想象一下，由于某种原因，你的编程语言不能完成相同的加法，那么图灵机是不完整的。 另一方面，如果它可以运行像通用图灵机可以运行的任何程序，那么它是图灵完整的。
大多数现代编程语言，如Java，JavaScript，Perl等都是完整的，因为它们全部实现了运行程序所需的所有function，如加法，乘法，if-else条件，返回语句，存储/检索/擦除数据的方式等。
更新：您可以在我的博客文章中了解更多： “JavaScript是图灵完整” – 解释
它经常被用来定义“真正”的编程语言，在那里你可以expression任何计算。 检查一些不能expression所有计算的语言可以帮助：
- SQL
- 正则expression式
- 你input你的四function计算器的语言
- XML
- 任何编程语言，当限制到1KB的内存（或任何有限的内存）。
非图灵完整语言的wikipedia
从根本上说，图灵完备性是一个简洁的要求，无限recursion。
甚至没有记忆。
我独立思考这个问题，但是这里是对这个断言的一些讨论 。 我对LSP的定义提供了更多的上下文。
这里的其他答案并不直接界定图灵完备性的基本本质。
图灵完成意味着它至less与图灵机一样强大。 这意味着图灵机可以计算的任何东西都可以通过图灵完整系统来计算。
还没有人发现比图灵机更强大的系统。 所以，暂时说一个系统是图灵完全的就像说系统是一样强大的任何已知的计算机系统（见教会 – 图灵论文 ）。
简而言之，图灵完备系统可以解决任何可能的计算问题。
其中一个关键的要求是便签本的大小是无限的，并且可以倒带以访问对便签本的先前写入。
因此实际上没有一个系统是图灵完成的。
相反，有些系统通过build模无限存储器并执行任何可能适合系统内存的计算来逼近图灵完备性。
我认为“图灵完整”概念的重要性在于能够识别一个计算机器（不一定是机械/电子“计算机”），它可以将其过程解构成简单的指令，由简单和简单的指令，通用机器可以解释然后执行。
我强烈推荐The Annotated Turing
@Mark我认为你所解释的是通用图灵机和图灵完成的描述之间的混合。
从实际意义上来说，图灵完成的东西将是一个机器/过程/计算，可以被写入和表示为一个程序，由一个通用机器（一台台式计算机）来执行。 虽然它没有考虑时间或存储，正如别人所说的。
正如Waylon Flinn所说 ：
图灵完成意味着它至less与图灵机一样强大。
我相信这是不正确的，如果一个系统完全像图灵机一样强大，那么系统就是图灵完备的，也就是说，机器完成的每一个计算都可以由系统来完成，而且系统完成的每一个计算都可以通过图灵机完成。
在大多数程序员所熟悉的实用语言术语中，检测图灵完备性的常用方法是，如果语言允许或者允许模拟嵌套的无界while语句（与带有固定上限的Pascal风格语句相反）。
关系数据库可以input地点和道路的纬度和经度，并计算它们之间的最短path – 不。 这是一个显示SQL不是图灵完整的问题。
但是C ++可以做到这一点，并可以做任何问题。 因此是。
