本文转自豆瓣_燃烧的影子
图灵机与可计算性
图灵（1912~1954）出生于英国伦敦，19岁进入剑桥皇家学院研究量子力学和数理逻辑。1935年，图灵写出了“论高斯误差函数”的论文，因此他从一名学生直接成为学院的研究员，并开始了“可计算性”研究。1936年4月，图灵发表了“可计算数及其在判定问题上的一个应用”的论文，形成了“图灵机”的重要思想。用反证法证明，任何可计算其值的函数都存在相应的图灵机；反之，不存在相应图灵机的函数就是不具有可计算其函数值算法的函数。同年，图灵到美国普林斯顿大学学习，并于1938年获该校博士学位。1939年秋，图灵应召到英国外交部通信处从事密码破译工作，开始了最早的计算机的研究工作。战后图灵一直从事计算机的理论研究和实践开发研究，制作出最早的电子计算机。他于1950年发表了“计算机和潜力”的论文，引发了“机器是否会思考”的学术讨论，并成为影响至今的经典论著。图灵思想活跃，但性格内向，一直没有结婚。1954年6月，图灵在家中因氰化钾中毒去世，原因则众说纷纭，至今仍为一个谜。
“算法”（Algorithm）这个名称最早源于9世纪阿拉伯数学家花拉子米的一本著作，在这本著作中花拉子米用算法来概括算术四则运算的法则。20世纪初，希尔伯特提出了著名的23个数学问题，其中很多都涉及到问题解决的判定问题。1935年，正在剑桥皇家学院读书的图灵，在听了数理逻辑学家纽曼的课程后，开始注意希尔伯特的判定问题，并进行了潜心的研究。该问题要求判定是否存在一种有效的算法（或今天在计算机科学中称为“程序”的东西），把某个结论从一组给定的假设中用逻辑方法推演出来。图灵将算法看做一个机械的过程，或者是一组规则，它规定了人们在任何情况下必须执行的某类操作的指令。
今天的计算机技术，人们将“算法”定义为用特定的计算机语言编写的计算机程序。然而，图灵的早期研究则是为了从理论上解决可判定性来定义“算法”，并提出与之相应的图灵机（理论）。
图灵机是假设的抽象“计算机”，如图9.6所示。图灵机由三个部分组成：一条带子，一个读写头和一个控制装置。带子分成许多小格，每小格可存一位数（0或1），也可以是空白的。机器的运作是按逐步进行的方式，每一步由三个不同的动作组成：在任一确定时刻，读写头对准带子上的一个方格，根据该格上的内容和机器的状态决定自己的动作；机器可以抹去带上的原有符号，使方格保持空白或者写上另外的（也可以与原来相同的）符号；然后让带子通过读写头，朝两个方向之一移动一个方格。机器的行为自始至终是由一个指令集所决定，它明确地指示机器每一步应该执行哪三个动作。整个运作从读写头视读第一个方格数据开始，一旦计算结束，机器就进入一个特别的停止状态。运算过程的任何结果都被纪录在带子上。
非确定型图灵机
图9.6 图灵机的图示
图灵机的行为由算法控制，算法的程序由有限条指令组成，每一条取自下列一组可能的选择：
PRINT 0 ON THE CURRENT SQUARE 在当前方格中写0
PRINT 1 ON THE CURRENT SQUARE 在当前方格中写1
GO LEFT ONE SQUARE 左移一格
GO RIGHT ONE SQUARE 右移一格
GO TO STEP i IF THE CURRENT SQUARE CONTAINS 0 若当前方格内容为0，转向步i
GO TO STEP j IF THE CURRENT SQUARE CONTAINS 1 若当前方格内容为1，转向步j
STOP 停止
由这七种简单的指令出发，可以组成所谓的“图灵一波斯特程序”，通过这些程序控制机器完成各种计算。图灵机是一个假想的计算模型，并不是一台实际的机器。从以上介绍可见，它的结构与动作极为简单，但是，正是这样简单的结构包含了现代电子计算机最基本的工作原理：按串行运算、线性储存方式进行符号处理。
利用可计算性，数学家解决了众多的判定性问题，存在（或不存在）某种求解的算法，是确定这些判定性问题的标准。显然算法的存在性判定可以满足纯数学研究的需要。但另一方面，在解决现实问题中，单纯的算法存在性的判定是远远不够的。如果一个算法让高速计算机算上几千年，那么它就毫无实用的价值。我们必须研究有效算法的存在性，制定算法有效性的评估标准。
20世纪60年代，柯勃汉与爱德华兹创立了算法有效性的一种判定法则：区分算法是否有效，要以图灵机为基本的计算工具，用图灵机上完成计算的步数（即图灵程序）来评估一个算法是否有效。一般地，人们习惯于依据“计算时间”的长短来判定算法的有效性，使用这种度量标准，需要使用以下的相关定义：
如果存在确定的整数A和k，对于长度为n的输入数据，计算可以在至多Ank步内完成（对任意的n值）。那么，这个算法被称为“多项式时间算法。”例如，将两个整数相加的标准算法是多项式时间算法。不是多项式时间算法的算法被称之为“指数时间算法”。当一个算法处理长度为n的输入数据时，若需要2n（或3n， nn， n!）步，它就是一个指数时间算法。
柯勃汉和爱德华兹将“有效”算法规定为需要多项式时间的算法。而将需要指数时间的算法规定为“非有效”算法。这种划分方法只是“理论”的划分方法，它与实际应用还有一定的区别。譬如，A=1050和k=500的多项式时间算法在实际意义上一般不会“有效”。所幸的是，在现实问题中，一般都取10n3（即A=10， k=3）或更少步数的多项式时间算法或指数时间算法。尽管2n步算法在“理论上无效”但对适度小的n， 2n的步数完全可以比多项式时间更少。虽然对于不太大的n，多项式函数值可以超过指数函数值，但对于相对大的n，后者总是大于前者。假定一台计算机每10-6秒执行一次基本运算，对于已知的数据长度n，多项式时间与指数时间算法在计算机上的运行时间如下表：
非确定型图灵机时间－ 数据长度：n
复杂性函数 10 20 30 40 50 60
非确定型图灵机n 0.00001s 0.00002s 0.00003s 0.00004s 0.00005s 0.00006s
n2 0.0001s 0.0004s 0.0009s 0.0016s 0.0025s 0.0036s
n3 0.001s 0.008s 0.027s 0.064s 0.125s 0.216s
2n 0.001s 1.0s 17.9分 12.7天 35.7年 366世纪
3n 0.059s 58分 6.5年 3855世纪 2×108世纪 1.3×1013世纪
非确定型图灵机
目前，人们将多项式时间算法问题称为P型问题，它是可解的。但是诸如旅行推销员这类问题还不能说是无解的，而是归入了称之为NP型问题，NP意思是“非确定型多项式时间”，这样P型问题就是NP型问题的子集。为了理解NP这个概念，可以设想有一台图灵机或者其他任何一种计算机，它能在运算的各个步骤进行随机猜想。利用这样的假想计算机（称做非确定型图灵机），推销员问题就能用多项式时间求解：首先猜测第一个要访问的城市，然后猜第二个，第三个，如此等等，直到猜完整个旅行路线，然后计算总的路程并与已知旅差费假定值比较。只要机器每一步都“猜测正确”，最后所得的结果也就正确。这就是所谓NP型问题的涵义：通过一次或多次“正确的”（或“最优的”）猜想，问题可能在非确定型图灵机上用多项式时间求解。
由于数学内部与现实中存在着大量的既没有找到有效算法但又属于NP型的问题。人们希望解决这些问题的企图，转化为P是否能等于NP的理论讨论。1971年，库克借助图灵和他人的工作，运用抽象的方法证明了“NP型问题极不可能用多项式时间算法求解”。他的解释是：如果一类特殊的NP型问题（如旅行推销员问题）可以用多项式算法求解，那么所有NP型问题都可以用多项式时间求解。即库克认为“P不等于NP”。然而，要获得问题的最终解决，还需要一个反例，即找出一个属于NP型问题，又能证明它不是P型的问题，尽管P和NP这两个概念直觉有别，P不等于NP这个问题，但问题却还远没有得到解决，并且各方面的迹象都表明这是一个极其难以解决的问题。这个以“P=NP”著称的问题，已经成为当今计算机数学中最重要的未解决问题之一。
图灵机理论还成为人工智能的研究基础。根据符号转换的定义，人脑或计算机进行的定理证明、文字处理和一切可归结为符号处理的操作，都属于计算的过程。1947年，图灵在一次计算机会议上提出有关智能机器的报告，论证了智能机器的可能性。他的这篇报告被编入《机器智能》（1969年）后，人们才认识到它的深刻意义。1950年图灵又根据计算机能进行符号计算的事实，发表了《计算机与智力》的重要论文，提出计算机能像人类的思维方式进行思维的观点，并给出了检验计算机是否具有思维的能力的一个实验，这就是很著名的“图灵检验”。1956年夏，美国的一批年轻的科学家讨论了用机器模拟人类智能的问题，提出人工智能的概念。1976年西蒙等人提出了物理符号假设：任何一个系统，如果它能表现出智能，则它必须具备执行输入符号、输出符号、存储符号、复制符号、建立符号结构和条件性迁移操作这六种功能。反之，任何能执行这六种操作的系统，必然表现出智能，这一假设有三个推论：第一，因为人有智能，所以人是一个符号系统；第二，因为计算机是一个符号系统，所以计算机可以表现出智能；第三，计算机能模拟人的职能。该假设为人工智能提供了一个理论基础，其核心思想是，智能可以归结为六种操作符号或计算。
1991年11月8日，波士顿计算机博物馆举行了世界第一次的图灵试验，让人与8种程序计算机交谈，话题包括女人的衣着，亲属关系，以及白兰地酒等。这次实验将计算机与人的对话变成了现实。
1形式化定义2停机问题3通用图灵机4变体5图灵可计算性6其它等价的计算…
形式化定义
一台图灵机是一个七元组 (Q,Σ,Γ,δ,q0,qaccept,qreject)，其中 Q,Σ,Γ 都是有限集合，且满足
1.Q 是状态集合；
2.Σ 是输入字母表，其中不包含特殊的空白符 □；
3.Γ 是带字母表，其中 □∈Γ且Σ∈Γ ；
4. δ:Q×「→Q×Γ×{L,R}是转移函数，其中L,R 表示读写头是向左移还是向右移；
5.q0∈Q是起始状态；
6. qaccept是接受状态。
7.qreject是拒绝状态，且 。 qreject≠qaccept
图灵机 M = (Q,Σ,Γ,δ,q0,qaccept,qreject) 将以如下方式运作：
开始的时候将输入符号串 从左到右依此填在纸带的第 号格子上， 其他格子保持空白(即填以空白符)。 M 的读写头指向第 0 号格子， M 处于状态 q0。 机器开始运行后，按照转移函数 δ 所描述的规则进行计算。 例如，若当前机器的状态为 q，读写头所指的格子中的符号为 x， 设 δ(q,x) = (q',x',L)， 则机器进入新状态 q'， 将读写头所指的格子中的符号改为 x'， 然后将读写头向左移动一个格子。 若在某一时刻，读写头所指的是第 0 号格子， 但根据转移函数它下一步将继续向左移，这时它停在原地不动。 换句话说，读写头始终不移出纸带的左边界。 若在某个时刻 M 根据转移函数进入了状态 qaccept， 则它立刻停机并接受输入的字符串； 若在某个时刻 M 根据转移函数进入了状态 qreject， 则它立刻停机并拒绝输入的字符串。
注意，转移函数 δ 是一个部分函数， 换句话说对于某些 q,x， δ(q,x) 可能没有定义， 如果在运行中遇到下一个操作没有定义的情况， 机器将立刻停机。
停机问题
停机问题（halting problem）是目前逻辑数学的焦点，和第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的(countable) S 也是可停机的，在使用 oracle 输入的帮助下。
通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，可以有一个程序判断其本身是否会停机并做出相反的行为。这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。
停机问题本质是一阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。！
证明:
设停机问题有解，即：存在过程H(P, I)可以给出程序P在输入I的情况下是否可停机。假设若P在输入I时可停机，H输出“停机”，反之输出“死循环”，即可导出矛盾：
显然，程序本身可以被视作数据，因此它可以被作为输入，故H应该可以判定当将P作为P的输入时，P是否会停机。所以我们设过程K(P)的流程如下：首先，它调用H(P, P)，如果H(P, P)输出“死循环”，则K(P)停机，反之K(P)死循环。即K(P)做与H(P, P)的输出相反的动作。
现在假设求K(K)，则若H(K, K)输出停机，K(K)死循环，但由定义知二者矛盾。反之，H(K, K)输出死循环，则K(K)停机，两者一样矛盾。
因此，H不是总能给出正确答案，故而不存在解决停机问题的方法。
通用图灵机
对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。 我们用
NP："非确定性图灵机下"的多项式算法
举个例子.
假设你丢了一颗巧克力，你首先猜测,”巧克力书桌的抽屉里“，你从现在的位置（如客厅）走到书桌旁，打开抽屉，一看，有两种结果：
没有.继续猜测“可能在你爸的抽屉里”,..., 寻找...
有.
每一次寻找，你可能找不到，也可能找到,你不能确定. 但每一次寻找都可以在短时间内完成。
不确定性图灵机下的P算法，也大致如此.
NP完全性问题
在学习算法设计与分析时，经常会提到NP完全性问题，到底什么是NP完全性问题? ...
NP完全性问题属于"计算复杂性"研究的课题。 所谓计算复杂性，通俗说来，就是用计算机求解问题的难易程度。其度量标准有两个：一是计算所需步数或者指令数(时间复杂度)；二是计算所需的存储单元数(空间复杂度)。它不是对一个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类，即复杂性类。
再强调一下，问题的复杂性和算法的复杂性的区别是：只就时间复杂性来说，算法的复杂性是指解决一个问题的算法执行的时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度。计算复杂性要研究的是后者。
如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则称这种可以在多项式时间内解决的判定性问题属于p类问题。p类问题就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间的算法(或许根本不存在)，比如"找出无向图中哈密尔顿回路"问题。但是我们发现如果给了我们该问题的一个答案，就可以在多项式时间内判断这个答案是否正确。给出一个任意的回路，我们很容易判断它是否是哈密尔顿回路(只要看是不是所有的顶点都在回路中就可以了)。这种可以在多项式时间内验证一个解是否正确的问题成为NP问题，又称易验证问题类。
简单地说，存在多项式时间的算法的一类问题称为P类问题；而像梵塔问题、推销员旅行问题等，至今没有找到多项式时间算法解的一类问题，称为NP类问题。
复杂性理论中最具理论意义的当数NP完全性问题(NPC问题)，即由于"P=NP是否成立"这个问题难以解决，从NP类的问题中分出复杂性最高的一个子类，把它叫做NP完全类。已经证明，任取NP类中的一个问题，再任取NP完全类中的一个问题，则一定存在一个具有多项式时间复杂性的算法，可以把前者转变成后者。这就表明，只要能证明NP完全类中有一个问题是属于P类的，也就证明了NP类中的所有问题都是P类的，即证明了P=NP。
目前已知的NP完全性问题就有2000多个，在图上定义的许多组合优化问题是NP完全性问题，如货郎问题、调度问题、最大团问题、最大独立集合问题、Steiner树问题、背包问题、装箱问题等，遇到这类问题时，通常从以下几个方面来考虑，并寻求解决办法：
(1) 动态规划法：较高的解题效率。
(2) 分枝限界法： 较高的解题效率。
(3) 概率分析法： 平均性能很好。
(4) 近似算法： 近似解代替最优解。
(5) 启发式算法：根据具体问题的启发式搜索策略在求解，在实际使用可能很有效，但有时很难说清它的道理。关于P，NP，NPC和NP-hard的通俗解释
转自 http://hi.baidu.com/rangemq/blog/item/d55df0fc3c19f2f8fd037f48.html
P: Polynomial Solvable
NP: Non-determinstic Polynomial Solvable
0)词语解释：
Polynomial 【数】多项式的； 由平方，立方等常数次方或者更小的运算符和+,-,*,/等构
成的式子及其这种式子的和
Non-deterministic: 非确定性的;
Turing-machine: 图灵机; 英国数学家图灵提出的计算模型, 一个两端无限长的由小格子组
成的带子，每个格子可以存储一个数，一个可以在带子左右移动的游标或者指针或者不如叫
磁头(head), 磁头可读或修改格子里的数。 下面默认说的是确定性图灵机，和非确定性图
灵机功能上等价
Algorithm: 算法。 给定一个问题的描述作为输入，图灵机求解的过程。 此过程有可能无
限步长，则图灵机永远不会停止，除非被外部力量终止。
Polynomial algorithm: 多项式算法。 如果给定问题输入的长度，常量n, 则如果图灵机
解答过程需要的是时间是以n为变量的多项式，则这个解法（也是个算法）是有多项式的时
间复杂度的。
Decision question: 判定问题。 答案是yes或者no的问题
1) P问题和NP问题
P问题 (Polynomial Solvable):
如果一个判定问题是P问题，则这个问题存在一个多项式解法。 即图灵机只需要多项式时间
就可以得到答案, 既回答yes或者no。
NP问题(Nondeterminstic Polynomial Solvable):
如果一个判定问题是NP问题， 则这个问题的一个可能的解，可以在多项式时间内被验证是
否正确。 其实这不是本来的定义。 本来的定义是，NP问题是非确定性图灵机有多项式解。
但我们可以把非确定性图灵机多项多可解转化成确定性图灵机多项式可验证解。 确定性
图灵机更好好理解，所以用那个定义。
P问题是确定性图灵机在多项式时间内求到解，NP问题是非确定性图灵机在多项式时间内求
到解，或者说NP问题是确定性图灵机在多项式时间内验证解.
所以NP问题比P问题更难。 就像前面有人说的，改卷的老师会验证题目的答案是否正确，
但他不一定会做这些题。
2) 关系
P 属于 NP。 就是说，一个问题如果属于P， 则一定属于NP。 (这里P, NP表示符合定义的
相关问题的集合)
反过来则不一定，7大数学世纪难题之一就是问 P是否等于NP。
3) NPC 和 NP-hard
NPC, 即NP完全性问题。 是指NP问题中的最难的问题。 即还没有找到多项式解法，但多项
式可验证。 而且只要一个NPC问题有多项式解法，其它所有NP问题都会有一个多项式解法。
NP-hard是指所有还没有找到多项式解法的问题, 并没有限定属于NP。 所以NP-hard比
NPC范围更大，也会更难。 NPC是NP-hard和NP的交集.
图灵机
1936年，阿兰·图灵提出了一种抽象的计算模型 —— 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
在纸上写上或擦除某个符号；
把注意力从纸的一个位置移动到另一个位置；
而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：
一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。
一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。
一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程
自动机
automata
对信号序列进行逻辑处理的装置。在自动控制领域内，是指离散数字系统的动态数学模型，可定义为一种逻辑结构，一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中，分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。在语言学中则把自动机作为语言识别器，用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型，用来研究神经生理活动和思维规律，探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型，研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数，研究各种算法。现代自动机的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。自动机可按其变量集和函数的特性分类，也可按其抽象结构和联结方式分类。主要有：有限自动机和无限自动机、线性自动机和非线性自动机、确定型自动机和不确定型自动机、同步自动机和异步自动机、级联自动机和细胞自动机等。
参考资料：http://www.swarmagents.com/javaclass/ca.htm
图灵机（英语：Turing Machine，又称确定型图灵机）是英国数学家阿兰·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
一台图灵机是一个七元组 (Q,Σ,Γ,δ,q0,qaccept,qreject)，其中 Q,Σ,Γ 都是有限集合，且满足
Q 是状态集合；
Σ 是输入字母表，其中不包含特殊的空白符 ；
Γ 是带字母表，其中 且 ；
是转移函数，其中L,R 表示读写头是向左移还是向右移；
是起始状态；
是接受状态。
是拒绝状态，且 。
图灵机 M = (Q,Σ,Γ,δ,q0,qaccept,qreject) 将以如下方式运作：
开始的时候将输入符号串 从左到右依此填在纸带的第 号格子上， 其他格子保持空白(即填以空白符)。 M 的读写头指向第 0 号格子， M 处于状态 q0。 机器开始运行后，按照转移函数 δ 所描述的规则进行计算。 例如，若当前机器的状态为 q，读写头所指的格子中的符号为 x， 设 δ(q,x) = (q',x',L)， 则机器进入新状态 q'， 将读写头所指的格子中的符号改为 x'， 然后将读写头向左移动一个格子。 若在某一时刻，读写头所指的是第 0 号格子， 但根据转移函数它下一步将继续向左移，这时它停在原地不动。 换句话说，读写头始终不移出纸带的左边界。 若在某个时刻 M 根据转移函数进入了状态 qaccept， 则它立刻停机并接受输入的字符串； 若在某个时刻 M 根据转移函数进入了状态 qreject， 则它立刻停机并拒绝输入的字符串。
注意，转移函数 δ 是一个部分函数， 换句话说对于某些 q,x， δ(q,x) 可能没有定义， 如果在运行中遇到下一个操作没有定义的情况， 机器将立刻停机。