一、从PHP与Python的语言比较去了解什么是图灵完备

从非常严格的理论角度来说，答案是：没有。因为PHP和Python都是图灵完备(Turing complete)的语言，所以理论上你找不到一个Python能做到而PHP做不到的事情。

可图灵指在可计算性理论中，编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之，此系统可与通用图灵机互相模拟。这个词源于引入图灵机概念的数学家艾倫·图灵（Alan Turing）。

虽然图灵机会受到存储能力的物理限制，图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。

简单来说，一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。

图灵等价02Turing equivalence02和图灵完备02Turing completeness

经常在讲编程语言的书或文章里面看到图灵等价（Turing equivalence）和图灵完备(Turing completeness)，但却不知道这两个词的精确含义和区别。尤其是很多书或文章经常对这两个词进行混用，我就很疑惑这两个词是不是就是一个意思。我用Google搜索了一下，很遗憾的是中文结果基本没用，只有一篇百度空间里面转载的一个外国人写的文章，还是全英文的，简单看了下感觉写得不怎么清楚，就查了下英文维基百科。言归正传，下面先看看维基百科的两段话：

In02computability theory, a system of data-manipulation rules(such as an02instruction set, a02programming language, or a02cellular automaton) is said to beTuring complete02or02computationally universal02if and only if02it can be used to simulate any single-taped02Turing machine02and thus in principle anycomputer.

在可计算理论里，一个数据操作规则的系统（比如：指令集、编程语言、细胞自动机）被称作图灵完备或者通用计算的，当且仅当它可以被用来模拟单带图灵机。

In computability theory, there is a closely related concept known as Turing equivalence. Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P. Thus, a Turing-complete system is one that can simulate a Turing machine, but the term is most often used to mean Turing equivalent to a Turing machine.02

在可计算理论里，有一个很相关的概念叫图灵等价。当计算机 P和计算机 Q是图灵等价的，当P可以模拟Q而且Q也可以模拟P。因此，一个图灵完备的系统可以模拟图灵机，但是这个术语（即图灵等价）常常被用来指与图灵机等价。

然后我们再来看看在可计算理论中，这两个词的正式定义：

Turing completeness：A computational system that can compute every Turing-computable function02is called Turing complete(or Turing powerful). Alternatively, such a system is one that can simulate a02universal Turing machine.

Turing equivalence：A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable; i.e., it computes precisely the same class of functions as do02Turing machines. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine.(All known Turing-complete systems are Turing equivalent, which adds support to the02Church–Turing thesis.)

图灵等价：一个图灵完备的系统被称为图灵等价的，如果任何它可以计算的函数也是图灵可计算的。也就是它可计算的函数和图灵机可计算的函数是完全相同的。换句话说，就是图灵等价的系统就是能模拟通用图灵机同时也能也被通用图灵机模拟的系统。（所有已知的图灵完备的系统都是图灵等价的，这增加了对丘奇-图灵论题的支持）

通过上面的分析，我们就可以清楚的知道这两个词的意思和关系了。图灵等价有两个意思，一个是指两个计算系统在可计算性上计算能力相同；另一个，也是常用的一个就是指一个系统的计算能力与通用图灵机计算能力相同（在可计算性的意义上）。而图灵完备是指能够模拟通用图灵机的计算系统。而所有已知的图灵完备的系统都是图灵等价的，这也增加了对丘奇-图灵论题的支持。因此，在现有的计算机系统（编程语言、指令集等）上，使用图灵等价和图灵完备是一个意思。

二、什么是图灵机和通用计算机

图灵机，又称图灵计算机，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。对于任意一个图灵机，因为它的描述是有限的，因此总可以用某种方式将其编码为字符串。，用<M>表示图灵机 M的编码。

通用计算机是指各行业、各种工作环境都能使用的计算机。通用计算机适应性很强，应用面很广，但其运行效率、速度和经济性依据不同的应用对象会受到不同程度的影响。通用计算机不但能办公，还能做图形设计、制作网页动画、上网查询资料等。

扩展资料：

图灵提出图灵机的模型的意义：

1、它证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计算机应有的主要架构；

2、图灵机模型引入了读写与算法与程序语言的概念，极大的突破了过去的计算机器的设计理念；

3、图灵机模型理论是计算学科最核心的理论，因为计算机的极限计算能力就是通用图灵机的计算能力，很多问题可以转化到图灵机这个简单的模型来考虑。

参考资料来源：百度百科-图灵机

参考资料来源：百度百科-通用计算机

三、大家经常说的“图灵完备”是什么意思有什么用

图灵完备，图灵完全性一般情况下指的是有无限存储能力的通用物理机器或编程语言。图灵完备就代表着你的语言能做到用图灵机能做到的所有事情，能够解决所有的可计算问题。图灵不完备也并不是就没有用了,有些场景我们要限制语言本身.如限制循环和递归,这样就能够确保语言能写的程序一定是终止的。简单来说的话，就是说图灵完备的语言，有循环执行语句，判断分支语句等。理论上可以解决任何算法。但有可能进入死循环而程序瘫痪。图灵不完备，应该是不允许或限制循环。能够确保的是，每段程序都不会死循环，都有运行完的时候。比特币的脚本系统是图灵不完备的，而一些竞争币的智能合约系统是图灵完备的。他们有各自的优势和劣势，图灵不完备会更安全一点，图灵完备会更智。一点

我们通过以上关于大家经常说的“图灵完备”是什么意思有什么用内容介绍后,相信大家会对大家经常说的“图灵完备”是什么意思有什么用有一定的了解,更希望可以对你有所帮助。

四、图灵完备是什么意思

机器执行任何其他可编程计算机能够执行计算的能力。图灵完备是指机器执行任何其他可编程计算机能够执行计算的能力。简单来说，一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。这个词源于引入图灵机概念的数学家艾伦·图灵。

五、图灵机是什么东西啊

其实呢，图灵机的来历忒单纯。以前一个叫图灵的闲人养了只无所事事的小母鸡。图灵成天忙着跑马拉松，懒得照顾它，就装了条在鸡看来无限长分格的传送带，定时传送食物和水。而鸡闲来无聊，便走来走去，在带子上摆放物事，权作耍子。郁闷时在格子里放根树枝。兴奋了在某个格子里下个蛋。想起了还可以把蛋换成树枝，或者把树枝换成蛋。不高兴了在传送带上扔颗石头，于是传送带就卡住了。某天小母鸡不小心把一株野生大麻当鸡骨草吞了，high得不行，绕着传送带发疯：

在传送带靠左的地方放下一根树枝一个蛋：10

在传送带靠右的地方放下两根树枝：11

回到左边，把树枝拣起来，再把蛋换成树枝：1

回到右边，把两根树枝换成一根树枝两个蛋：100

回到左边，把树枝拣起来

回到右边，把最右边的蛋换成树枝：101

这下左边的树枝和蛋都没了。小母鸡意兴索然，一怒之下扔颗石头卡死机器。

刚从杂货店提了袋苹果的图灵路过，目睹这一切。不由灵光一现：这不2+3=5么？原来加法还可以这么玩儿啊！以后不用为算帐发愁了。不过图灵的兴趣不在算帐，而在玩儿tic-tac-toe。问题是小母鸡智力有限。要她理解tic-tac-toe这样的东东还不如让公牛上树兔子下蛋。幸好图灵是个好琢磨的勤快人，没事喜欢读一个叫Kurt Godel的德国人的文章。而Godel崇拜一个叫David Hilbert的老乡。Hilbert在德国哥廷根讨生活时没事喜欢玄想，一不小心在世纪之交提出23个问题。居然引得此后100年来无数闲人神魂颠倒。Godel对第10个问题着了迷。研究几年后，写了篇帖子总结心得，顺便告诉大家，Hilbert也有猜错的时候。第10个问题的答案是我们不能依靠形式化方法找到所有丢番都方程的解。而推论就是大家就不用指望设立几个事实（闲人们管这叫公理），再用一套规则推出所有真理。“我们必须知道，我们必将知道”的难度比Hilbert预计的大多了。这一下彻底broke Hilbert’s heart。不过我跑题了。Godel的论文花了大量篇幅描述怎么用数字来表示自然数以外更复杂的东东（黑话叫encoding）。图灵应该看过这篇文章。他很快发现，用树枝和蛋完全可以模拟出tic-tac-toe。比如说四个蛋表示左上角画圈。三个蛋一根树枝, 0001，表示左上角画X。而且他证明了就算小母鸡吃了大力丸能用更复杂的符号在传送带上描述tic-tac-toe，也不过比她用树枝和蛋少花4log(|∑|)倍的时间而已。这里的|∑|代表一共有多少所谓的复杂符号。于是图灵写了帖子，介绍他的鸡。后人就把这只鸡叫图灵鸡了。而且人们惊奇地发现，虽然他们做出的机器越来越花哨，下国际象棋能让大尾巴狼卡斯帕罗夫肝肠寸断，失意江湖，也不过是一只摆放树枝和蛋时快如闪电的图灵鸡而已，和作古的正宗图灵鸡没有本质区别。我们为了纪念这个现象，就造了一专用名词，图灵等价。人们还观察到有些问题非图灵鸡不可，于是再造一词：图灵完备。现在很多老大喜欢把图灵完备和图灵等价混用。这好比说命题成立所以逆命题成立，多数时候不靠谱。不过这个话题值得单独写一帖子，以后再说吧。

图灵并不满足于简单的2＋3＝5和tic-tac-toe，所以他敏锐地注意到另一个重大挑战：如果每只鸡都只能做一种计算，他得养多少鸡组装多少传送带才能算帐啊？更别说下国际象棋了。人肉计算机图灵是做化繁为简的高手。这个高难问题被他举重若轻地解决了：首先他证明了任何图灵机都可以用树枝和蛋表达。然后他养了只更聪明的鸡(图灵搞了N年的数学生理学和形态发生学，大家知道是为什么了吧？)。这只鸡吃脑白金喝农夫山泉，嘛都不干，不打鸣不下蛋，但会识别理解用树枝和蛋描述的其它图灵机，并在传送带上模拟它们的操作。用闲人们的黑话总结，就是对任意问题x,和,总存在一只鸡U，使得。这里的是用a这串树枝加蛋的长列表示的图灵鸡。这样的鸡，一只顶一万只啊。从此，图灵不需要再养那么多鸡了，他只需用树枝和蛋摆出算帐的方法，和提供数据，这只鸡就能算出结果。想到这里，图灵只觉元气充沛，不禁仰天长啸：I do chicken right.这只新品种的鸡从此被称为元图灵鸡(Universal Turing Machine)。Universal者，我鸡一出百鸡杀之意也。元图灵鸡具有重大意义，代表了两大计算支柱（还有一个是self-reference）：universality，和duality。Universality我们才说了。而duality是说数据和程序本是如来佛祖座前绞在一块儿的两根灯芯。比如用树枝和蛋表示的图灵鸡，你说它是程序呢，还是数据？理论界的元老Martin Davis在他的书里甚至说储存程序的计算机这一革命性的概念就是起源于这只元图灵鸡。对了，当年英国有图灵这样的先驱，造出世界上第一台通用计算机，为什么到头来计算机历史让美国人独大呢？说来也是一段让人嗟叹的故事。一言以蔽之，笼中鸡不如走地鸡，走地鸡不如野鸡。有兴趣的可以读Andy Kessler的How We Got Here。这本书语言之生动，段子之幽默，故事之曲折，史料之有趣，实在不可多得。而且免费。不能不推荐的说。

当然，一只鸡是远远不够的。图灵在1952年写了一坨国际象棋程序，当时居然没有机器能跑动。很快闲人们一窝蜂扑向计算复杂性这个崭新的研究领域。4、50年前实在是烽烟四起的战国时代啊，到处是传奇英雄的传奇故事。好像随便什么领域都有震撼人心的发现。1964年，Alan Cobham和Jack Edmonds在ACM BBS上发帖，说如果一个问题能被一只图灵鸡用有限步骤解决，而解决的步数是这个问题长度的多项式，那么这个问题的复杂度就是P。P是Polynomial的缩写。可惜有些问题的算法远比P复杂，比如找出国际象棋对局的最佳策略。不过很快有人提出，有些问题虽然看似复杂，但验证这些问题的算法是否正确需要的复杂度却是P。比如判断一堆整数里面有没有几个整数的和刚好为0。验证某个可能答案太简单了：对答案里的数求和就行，花的时间最多等于这堆整数的个数。于是有达人就想：这样好办啊。如果一个问题的备选答案有N个，那我们就养它N只鸡，让每只鸡验证一个答案。如果每个答案的验证复杂度都是P，那最终的复杂度不也是P了么？可惜，得到验证结果前我们不知道哪个候选答案一定正确，也不能确定哪只鸡先得到答案，就好像不知道哪个女工先找到旺卡巧克力工厂的金券。为了和普通的图灵鸡区分，闲人们把这种兵团做战的鸡群叫做non-deterministic图灵鸡。因为用这种图灵鸡能在多项式时间内找到答案，所以我们把这种复杂度叫NP，也就是Non-deterministic Polynomial的简写。还是很直观的吧？很明显，P是属于NP的，因为既然我们能在P内找到答案，自然能在P内验证答案。那有没有属于NP但不属于P的呢？俺就不知道了。如果我知道的话，我就证明了P=NP或P!= NP，拿了Cray研究院的100万美元花红，到Bora Bora的海滩悠哉游哉地喝Pina Colada乐。

不能证明P是否等于NP没有打击闲人们的积极性。不知道是否等于总比知道不等于好吧？所以牛人们还是前赴后继地探索。于是NP-Hard就被提出来乐。NP-hard的概念也直观：我不知道你具体有多复杂，但我知道你至少和NP问题一样复杂。什么叫一样复杂呢？于是有牛人提出，反正多项式加上多项式还是多项式。所以可以判断，如果我们已知一个问题H的算法并且每一个属于NP的问题都可以在多项式时间内通过把玩H得出，那H就是NP-hard。也就是说，如果存在一个函数（或者算法）f,使得f(H)＝所有NP问题的集合，且计算f(H)的开销是P，那H就是NP-hard的。当然，我们还是可以让一只图灵鸡来执行这个函数，所以有函数f存在被称为图灵多项式可归约（polynomial time Turing reducible）如果H同时也属于NP，那H就是NP-Complete乐。我们可以相对容易地证明，如果有一个问题，哪怕只有一个问题，既属于NP也属于P，那整个P和NP就坍塌了，P＝NP。有兴趣的老大可以自己证明一下。到了这里，关于复杂性的研究好像被堵死了。确定一个问题是否为NP-Hard，就得证明它能被多项式归约到所有NP问题。简直就是mission impossible嘛。就在这存亡之际，出身水牛城安家多伦多的库克爷爷小宇宙爆发，于1971年证明了SAT问题（也就是判断什么样的集合能让一个布尔公式为1）属于NP-Complete。一时间众生颠倒。有了SAT垫底，我们就不用去对付所有的NP问题，而只需要对付规约到SAT这一相对简单得多的问题。到目前为止，属于NP-Complete的问题没有1000也有500了吧？人们还相继发现了其它复杂类。这里罗列了几乎所有的复杂类，共有462种。