什么是图灵完备的编程语言？

Question

什么是图灵完备的编程语言？

Answer 1

如果一个语言的计算能力和通用图灵机相当，那么就是图灵完全的。

• 通用图灵机 (维基百科)

虽然图灵机的概念很简单，但这是现代编程语言所能拥有的最高计算能力。

编程语言本质上都是在冯诺依曼体系结构的计算机上，对图灵机的抽象。所以，可以回答题主的疑问：现在的计算机编程语言都是图灵完全（完备）的。

因此，这世上也不存在一种语言可以做，而另一种语言不可以做的事儿（PS：不过，PHP仍然是世界上最好的编程语言）。

那有没有不是图灵完备的吗？有：

Answer 2

翻译一下上边那段英文.. 再简化一下, 就是能够模拟最初图灵机的那个纸带模型.
纸带模型具体细节参考 Wiki, 总之是鬼怎非常非常简单的一个模型,
它只能做移动, 写符号, 擦除这样一些基本的操作, 但这个模型是可以模拟所有的计算过程的.
的一门编程语言能模拟纸带模型的图灵机, 就是说也能够模拟所有的计算过程.
这样就完备了... 虽然很多还是数学上的内容.

大概要注意下, 我记得以前看网上经常会弄错, 就是把完备性当成一门语言能做各种功能
比如说处理文件, 处理网络, 能用正则, 或者模拟面向对象之类的.. 大致对应编程语言功能的涵盖..
完备性更多是数学上的概念, 后者跟完备性不是指一个事情.

Answer 3

http://en.wikipedia.org/wiki/Turing_completeness

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine. The concept is named after Alan Turing. A classic example is lambda calculus.

Answer 4

只有8条指令的图灵完备语言 http://en.wikipedia.org/wiki/Brainfuck

Answer 5

简单一点就是什么开发都能做的编程语言。
另迷渡老师的解答非常精彩(尤其是关于PHP的部分

Answer 6

这里有一篇不错的介绍文章 “从PHP与Python的语言比较去了解什么是图灵完备”
http://www.nowamagic.net/librarys/veda/detail/1856

Answer 7

所谓的图灵完备，是某些半吊子胡扯出来的玩意。它们经常一本正经地说“理论上Python能实现的，PHP都能实现，因为它们都是图灵完备的。”这种鬼话。其实，它们不懂什么是图灵完备，也没有人真的知道。总之，这就是个拿老虎扯皮的玩意。

你可以把php、python换成其他。实际上，你不可能用php来做一个操作系统，甚至做一段引导程序，甚至一个办公软件。

这种屁话，就跟我说，理论上，我能成为世界首富一样，无聊，浅薄。

现在网上充斥者这些垃圾文章，思想，作者一本正经的胡说八道，脱离实际，故作高深。

并不存在什么“图灵完备”。以后碰到这种胡扯的垃圾，远离就是。