https://stackoverflow.com/questions/7284
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
什么是表达"图灵完整"的意思吗？
你可以给一个简单的解释，而不需要太多的理论细节吗？
解决方案
这是最短的解释：
图灵完整的系统装置一个系统在这一程序可以写，将找到一个答复(尽管没有保证有关运行时或存储器)。
所以，如果有人说"我的新事物是图灵完整"，这意味着在原则(虽然往往没有在实践)它可用于解决的任何计算的问题。
有时就是它是一个笑话...一个家伙写了一个图灵机模拟器在六，所以可以说，六是只有计算机需要的世界。
其他提示
这里是最简单的解释
阿兰*图灵创造了一台机器，可以采取的程序和运行程序，并表现出一定的结果。但是然后他不得不建立不同的机对不同的程序。因此他创造了"普遍图灵机"，可以采取任何程序和运行。
编程语言中的类似机(尽管虚拟).他们采取的程序和运行它们。现在，一种编程语言中被称为"图灵完整"，如果它能运行的任何程序(不论其语言)，图灵机可以运行给予足够的时间和存储器中。
例如：让我们说有一个程序，需要10个数字，并增加了他们。图灵机可以很容易地运行这个程序。但现在想象一下，因为某些原因你的编程语言中不能这样做除了那是图灵机的不完整的。另一方面，如果它能运行的任何程序喜欢的普遍图灵机可以运行，那么它是图灵完成。
大多数现代化编程语言，如Java,JavaScript,Perl等都是图灵完成，因为他们所实施的所有功能运行所需的程序，如外，乘法，如果其他条件，返回的声明，方式来存储/检索/删除的数据等。
更新：你可以了解更多我的博客上职： "JavaScript是图灵完成"解释的
从 维基百科:
图灵完整性、名艾伦 图灵，是重要的，每一个 似乎合理的设计，计算 设备迄今为止高级可以模仿 通过一个通用图灵机一个 观察这已成为 教堂-图灵的论文。因此， 机器，可以作为一个普遍的 图灵机的可能，在原则上， 执行任何计算，任何其他 可编程的计算机能力。然而，这个有什么用 所需要的努力编写一个程序 为机器，它可能需要时间 为机器执行 计算，或任何能力 机可能拥有无关 来计算。
而真正的灵-完整的机器 是非常可能身体是不可能的， 因为他们需要无限制的储存， 图灵完整性往往是松散 归咎于身体或机 编程语言，这将是 普遍，如果他们有无限的 储存。所有的现代计算机 图灵完成在这个意义上。
我不知道你怎么可以更加非技术性的比，除了说"图灵完整的装置'能够回答可计算的问题给予足够的时间和空间'".
非正式定义
图灵完整的语言，是一个可以执行的任何计算的。的 教堂-图灵的论文 国家的任何品最终的计算可以通过一个图灵机。一个 图灵机的 是有机与无限的随机存取存储器和有限'程序'这一决定时，它应该读、写和通过记忆，当时它应当终止与某种结果，是它应该做的下一步。输入到一个图灵机是把它的存储器之前，它开始。
事情可能使语言不完整的图灵
图灵机可以作出决定，根据什么它认为，在存储器 -"语言"，只能支持 +, -, *, ， / 在整数是不是图灵完整的，因为它不能作出选择的基础上，其输入，但是图灵机能。
图灵机可以运行下去 -如果我们采取了Java,Javascript,或Python和删除的能力做任何形式的循环，GOTO，或功能的电话，也不会是图灵完整的，因为它可以不执行任意的计算，从来没有完成。 Coq 一个定理者，不能快速程序不终止，所以它不是图灵完成。
图灵机可以使用无限的记忆 -一语言是完全一样Java但将终止一次，它使用超过4千兆字节的记忆会不会是图灵完成，因为一个图灵机可以使用无限的记忆。这就是为什么我们实际上不能 建立 图灵机，但是仍然是一个灵完整的语言，因为Java 语言 没有限制，防止使用无限的记忆。这是一个原因，定期表达的不是图灵完成。
图灵机的随机存取存储器 -语言，只有让你工作与通过存储器 push 和 pop 操作一叠不会是图灵完成。如果我有一个"语言"，读一字符串 一旦 只能使用存储器通过推动和弹从一堆，就可以告诉我每一个 ( 字符串中都有其自己的 ) 后来通过推动时，看到 ( 和出现时，看到 ).然而，它不能告诉我如果每 ( 有其自己的 ) 稍后 和 每 [ 有其自己的 ] 后来(注意， ([)] 符合这一标准，但是 ([]] 不)。图灵机可以使用其随机存取存储器追踪 ()'s []'s分开，但是这种语言只有一堆无法做到。
图灵机模拟的任何其他图灵机的 -图灵机的，当时给予适当的'程序'，可以采取的另一个图灵机的'程序'和模拟它在任意的输入。如果你有一种语言，禁止从执行蟒蛇的口译，这不是图灵完成。
例的灵完整的语言
如果你的语言有无限的随机存取存储器，条件执行，某种形式重复的执行，它可能是图灵完成。有更多的异国情调的系统，仍然可以实现的一切图灵机的可能，这使得它们灵完成：
- 无类型的氧微积分
- 康威游戏人生
- C++模板
- 序言
简单的说,一个图灵完整的系统可以解决任何可能的计算问题。
其中一个关键要求是暂尺寸是无限的，这是可能的倒退访问之前写入暂存器。
因此在实践中没有一个系统是图灵完成。
而一些系统的近似图灵完整性，通过模拟无限制的存储器和执行任何可能的计算，以适合本系统内的记忆。
我认为重要的概念"图灵完成"是在识别能力的一个计算机(不一定是个机械/电气"计算机")，可以有其程序被解构成"简单"的说明，组成更加简单和更简单的指令，一项各国普遍加入机器可以解释并随后执行。
我强烈建议附加说明的图灵
@马克我认为你是什么解释是一个混合的描述之间的普遍图灵机和图灵完成。
东西那是图灵完成，在实际意义上将是一个机器/进程/计算能够编写的，并表示作为一个程序，以执行由普遍机(台式计算机)。虽然它并不需要考虑时间或储存，正如其他人。
我的理解简单的话说：
图灵完成： 一种编程语言/方案，可以做到的计算，是图灵完成。
例如：
你可以添加两个数字使用的只是 HTML.(Ans'没有'你必须使用javascript到执行。), 因此HTML不是图灵完成。
语言，如Java、C++、Python,Javascript,坚固为复仇等是图灵完成，因为你可以做到的计算增加两个数字使用这种语言。
希望这会有所帮助。
作为 伟伦Flinn说:
图灵完成意味着它至少是作为强大的作图灵机。
我相信这是不正确的，一个系统是图灵完整的，如果它恰恰是作为强大的图灵机，即每一个计算所做的机器可以通过该系统，而且每一个计算做了通过该系统可以通过图灵机。
在实际语言熟悉的，大多数程序员，通常的方式来检测图灵完整性是，如果该语言允许或允许仿真的嵌套的无限制的，同时声明(相对于帕斯卡尔风格的，为的声明，与固定上限).
可以有关系数据库输入的纬度和经度的地点和道路，以及计算最短它们之间的路径-没有。这是一个问题，显示SQL不是图灵完成。
但是，C++可以做到这一点，可以做任何问题。因此，它是。
