图灵机 什么是图灵机 知乎

图灵机与可计算性

图灵（1912~1954）出生于英国伦敦，19岁进入剑桥皇家学院研究量子力学和数理逻辑。1935年，图灵写出了“论高斯误差函数”的论文，因此他从一名学生直接成为学院的研究员，并开始了“可计算性”研究。1936年4月，图灵发表了“可计算数及其在判定问题上的一个应用”的论文，形成了“图灵机”的重要思想。用反证法证明，任何可计算其值的函数都存在相应的图灵机；反之，不存在相应图灵机的函数就是不具有可计算其函数值算法的函数。同年，图灵到美国普林斯顿大学学习，并于1938年获该校博士学位。1939年秋，图灵应召到英国外交部通信处从事密码破译工作，开始了最早的计算机的研究工作。战后图灵一直从事计算机的理论研究和实践开发研究，制作出最早的电子计算机。他于1950年发表了“计算机和潜力”的论文，引发了“机器是否会思考”的学术讨论，并成为影响至今的经典论著。图灵思想活跃，但性格内向，一直没有结婚。1954年6月，图灵在家中因氰化钾中毒去世，原因则众说纷纭，至今仍为一个谜。

“算法”（Algorithm）这个名称最早源于9世纪阿拉伯数学家花拉子米的一本著作，在这本著作中花拉子米用算法来概括算术四则运算的法则。20世纪初，希尔伯特提出了著名的23个数学问题，其中很多都涉及到问题解决的判定问题。1935年，正在剑桥皇家学院读书的图灵，在听了数理逻辑学家纽曼的课程后，开始注意希尔伯特的判定问题，并进行了潜心的研究。该问题要求判定是否存在一种有效的算法（或今天在计算机科学中称为“程序”的东西），把某个结论从一组给定的假设中用逻辑方法推演出来。图灵将算法看做一个机械的过程，或者是一组规则，它规定了人们在任何情况下必须执行的某类操作的指令。

今天的计算机技术，人们将“算法”定义为用特定的计算机语言编写的计算机程序。然而，图灵的早期研究则是为了从理论上解决可判定性来定义“算法”，并提出与之相应的图灵机（理论）。

图灵机是假设的抽象“计算机”，如图9.6所示。图灵机由三个部分组成：一条带子，一个读写头和一个控制装置。带子分成许多小格，每小格可存一位数（0或1），也可以是空白的。机器的运作是按逐步进行的方式，每一步由三个不同的动作组成：在任一确定时刻，读写头对准带子上的一个方格，根据该格上的内容和机器的状态决定自己的动作；机器可以抹去带上的原有符号，使方格保持空白或者写上另外的（也可以与原来相同的）符号；然后让带子通过读写头，朝两个方向之一移动一个方格。机器的行为自始至终是由一个指令集所决定，它明确地指示机器每一步应该执行哪三个动作。整个运作从读写头视读第一个方格数据开始，一旦计算结束，机器就进入一个特别的停止状态。运算过程的任何结果都被纪录在带子上。

图9.6图灵机的图示

图灵机的行为由算法控制，算法的程序由有限条指令组成，每一条取自下列一组可能的选择：

PRINT0 ONTHECURRENTSQUARE在当前方格中写0

PRINT1 ONTHECURRENTSQUARE在当前方格中写1

GOLEFTONESQUARE左移一格

GORIGHTONESQUARE右移一格

GO TO STEPiIF THECURRENT SQUARECONTAINS0若当前方格内容为0，转向步i

GO TO STEPjIF THECURRENT SQUARECONTAINS1若当前方格内容为1，转向步j

STOP停止

由这七种简单的指令出发，可以组成所谓的“图灵一波斯特程序”，通过这些程序控制机器完成各种计算。图灵机是一个假想的计算模型，并不是一台实际的机器。从以上介绍可见，它的结构与动作极为简单，但是，正是这样简单的结构包含了现代电子计算机最基本的工作原理：按串行运算、线性储存方式进行符号处理。

利用可计算性，数学家解决了众多的判定性问题，存在（或不存在）某种求解的算法，是确定这些判定性问题的标准。显然算法的存在性判定可以满足纯数学研究的需要。但另一方面，在解决现实问题中，单纯的算法存在性的判定是远远不够的。如果一个算法让高速计算机算上几千年，那么它就毫无实用的价值。我们必须研究有效算法的存在性，制定算法有效性的评估标准。

20世纪60年代，柯勃汉与爱德华兹创立了算法有效性的一种判定法则：区分算法是否有效，要以图灵机为基本的计算工具，用图灵机上完成计算的步数（即图灵程序）来评估一个算法是否有效。一般地，人们习惯于依据“计算时间”的长短来判定算法的有效性，使用这种度量标准，需要使用以下的相关定义：

如果存在确定的整数A和k，对于长度为n的输入数据，计算可以在至多An^k步内完成（对任意的n值）。那么，这个算法被称为“多项式时间算法。”例如，将两个整数相加的标准算法是多项式时间算法。不是多项式时间算法的算法被称之为“指数时间算法”。当一个算法处理长度为n的输入数据时，若需要2ⁿ（或3ⁿ，nⁿ，n!）步，它就是一个指数时间算法。

柯勃汉和爱德华兹将“有效”算法规定为需要多项式时间的算法。而将需要指数时间的算法规定为“非有效”算法。这种划分方法只是“理论”的划分方法，它与实际应用还有一定的区别。譬如，A=10⁵⁰和k=500的多项式时间算法在实际意义上一般不会“有效”。所幸的是，在现实问题中，一般都取10n³（即A=10，k=3）或更少步数的多项式时间算法或指数时间算法。尽管2ⁿ步算法在“理论上无效”但对适度小的n，2ⁿ的步数完全可以比多项式时间更少。虽然对于不太大的n，多项式函数值可以超过指数函数值，但对于相对大的n，后者总是大于前者。假定一台计算机每10^-6秒执行一次基本运算，对于已知的数据长度n，多项式时间与指数时间算法在计算机上的运行时间如下表：

时间－数据长度：n

复杂性函数102030405060

n0.00001s0.00002s0.00003s0.00004s0.00005s0.00006s

n²0.0001s0.0004s0.0009s0.0016s0.0025s0.0036s

n³0.001s0.008s0.027s0.064s0.125s0.216s

2n0.001s1.0s17.9分12.7天35.7年366世纪

3n0.059s58分6.5年3855世纪2×10⁸世纪1.3×10¹³世纪

目前，人们将多项式时间算法问题称为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种程序计算机交谈，话题包括女人的衣着，亲属关系，以及白兰地酒等。这次实验将计算机与人的对话变成了现实。

形式化定义

　　一台图灵机是一个七元组 (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不是总能给出正确答案，故而不存在解决停机问题的方法。

通用图灵机

　　对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。 我们用<M> 表示图灵机 M 的编码。
　　我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M 的编码<M>，然后模拟 M 的运作，这样的图灵机称为通用图灵机(Universal TuringMachine)。现代电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。但要注意,它只是模拟,因为现实中的计算机的存储都是有限的，所以无法跨越有限状态机的界限。

变体

　　图灵机有很多变种，但可以证明这些变种的计算能力都是等价的，即它们识别同样的语言类。证明两个计算模型 A 和 B 的计算能力等价的基本思想是： 用 A 和 B 相互模拟， 若 A 可模拟 B 且 B 可模拟 A，显然他们的计算能力等价。注意这里我们暂时不考虑计算的效率，只考虑计算的理论上“可行性”。
　　首先我们可以发现，改变图灵机的带字母表并不会改变其计算能力。例如我们可以限制图灵机 的带字母表为{0,1}，这并不会改变图灵机的计算能力，因为我们显然可以用带字母表为 {0,1} 的图灵机模拟带字母表为任意有限集合 Γ的图灵机。
　　另一个要注意的是，如果我们允许图灵机的纸带两端都可以无限伸展，这并不能增加图灵机的计算能力，因为我们显然可以用只有纸带一端能无限伸展的图灵机来模拟这种纸带两端都可以无限 伸展的图灵机。
　　如果我们允许图灵机的读写头在某一步保持原地不动，那也不会增加其计算能力，因为我们可以用向左移动一次再向右移动一次来代替在原地不动。
　　其它的常见图灵机变种包括：
　　多带图灵机
　　非确定型图灵机
　　枚举器

图灵可计算性

　　图灵可识别语言
　　图灵可判定语言
　　递归可枚举语言
　　可计算函数
　　递归函数
　　停机问题
　　可判定性
　　不可判定性

其它等价的计算模型

　　除了图灵机以外，人们还发明了很多其它的计算模型。包括：
　　寄存器机
　　递归函数
　　λ演算
　　生命游戏
　　马尔可夫算法
　　然而这些模型无一例外地都和图灵机的计算能力等价，因此邱奇，图灵和哥德尔提出了著名的邱奇-图灵论题：一切直觉上能行可计算的函数都可用图灵机计算，反之亦然。

NP："非确定性图灵机下"的多项式算法

举个例子.

1. 没有.继续猜测“可能在你爸的抽屉里”,...,寻找...
2. 有.

关于P，NP，NPC和NP-hard的通俗解释

图灵机

1936年，阿兰·图灵提出了一种抽象的计算模型 —— 图灵机 (TuringMachine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

在纸上写上或擦除某个符号；

把注意力从纸的一个位置移动到另一个位置；

而在每个阶段，人要决定下一步的动作，依赖于 (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) 可能没有定义， 如果在运行中遇到下一个操作没有定义的情况， 机器将立刻停机。



参考:http://zh.wikipedia.org/w/index.php?title=图灵机&variant=zh-cn

！！！非确定型图灵机

http://zh.wikipedia.org/wiki/非确定图灵机

！！！形式语言与自动机第一讲

http://wenku.baidu.com/view/c4e551c55fbfc77da269b10b.html

爱华网本文地址 » http://www.aihuau.com/a/25101015/282641.html