第二部分：图灵机

图灵机理论的提出及相关理论：

下面我们的主人公将是图灵，也许你现在对他一无所知，但阅读这一节后，你需要深刻的记住他，因为在我看来，是他启发与影响了他之后的整个计算机发展史。为了让大家更好地理解与接受他的理论，我会多穿插一些背景，毕竟天才也不是生活在真空中的。

图灵早年在剑桥大学求学，在那个年代，剑桥大学的大数学家罗素和怀特海已经创立了“数理逻辑学”。“数理逻辑”这个学科的创建，起源于一个逻辑上的“悖论”。为了非专业人士都能明白逻辑悖论的含义，哲学家或者数学家喜欢用讲故事的办法来解释它。一个经典的故事是：村子里有位理发师，他为而且只为村子里所有那些不给自己理发的人理发。数学的逻辑推理上会出现类似的悖论。数学家们十分担心“数学大厦”会因悖论的存在而坍塌，于是他们都想方设法去修补数学基础。例如，康托发表专著《集合论》，罗素与怀特海联合撰写三卷《数学原理》。

       剑桥大学是“数理逻辑学”的发源地与大本营，一群聪明而勤奋的青年数学家聚集在数学泰斗罗素教授的周围，图灵是其中的佼佼者。1935年，刚刚毕业，年仅23岁的图灵就被剑桥大学国王学院甄选为研究员，成为剑桥大学有史以来最年轻的研究员。正是图灵在数学，尤其是在“数理逻辑学”方面的深厚功底，令他几年后终于厚积薄发，一举奠定了他计算机科学的创始人的地位。

       图灵先知先觉，在电子计算机远未问世之前，他已经想到所谓“可计算性”的问题。物理学家阿基米得曾宣称:“给我足够长的杠杆和一个支点，我就能撬动地球。”类似的问题是，数学上的某些计算问题，是不是只要给数学家足够长的时间，就能够通过“有限次”的简单而机械的演算步骤而得到最终答案呢？这就是所谓“可计算性”问题，一个必须在理论上做出解释的数学难题。

       经过智慧与深邃的思索，图灵以人们想不到的方式，回答了这个既是数学又是哲学的艰深问题。1936年，图灵在伦敦权威的数学杂志上发表了一篇划时代的重要论文《可计算数字及其在判断性问题中的应用》。文章里，图灵超出了一般数学家的思维范畴，完全抛开数学上定义新概念的传统方式，独辟蹊径，构造出一台完全属于想象中的“计算机”，数学家们把它称为“图灵机”。这样的奇思妙想只能属于思维像“袋鼠般地跳跃”的图灵。

       “图灵机”想象使用一条无限长度的纸带子，带子上划分成许多格子。如果格里画条线，就代表“1”；空白的格子，则代表“0”。想象这个“计算机”还具有读写功能:既可以从带子上读出信息，也可以往带子上写信息。计算机仅有的运算功能是:每把纸带子向前移动一格，就把“1”变成“0”，或者把“0”变成“1”。“0”和“1”代表着在解决某个特定数学问题中的运算步骤。“图灵机”能够识别运算过程中每一步，并且能够按部就班地执行一系列的运算，直到获得最终答案。

       “图灵机”是一个虚拟的“计算机”，完全忽略硬件状态，考虑的焦点是逻辑结构。图灵在他那篇著名的文章里，还进一步设计出被人们称为“通用图灵机”的模型，它可以模拟其他任何一台解决某个特定数学问题的“图灵机”的工作状态。他甚至还想象在带子上存储数据和程序。“通用图灵机”实际上就是现代通用计算机的最原始的模型。

不过图灵在提出图灵机构想之后，又发现了新问题，有些问题图灵机是无法计算的。比如定义模糊的问题，如“人生有何意义”，或者缺乏数据的问题，“明天3D中奖号是多少”，其答案当然是无法计算出来的。但也有一些定义完美的计算问题，它们亦是不可解的，这类问题称为不可计算问题。

不可计算的问题在实践中几乎碰不到，事实上，很难找到这样的例子，既不可计算但又有人向计算的明确定义的问题。一个罕见的问题是所谓的停机问题。设想要编写一个用于检查并判定另一个程序是否会运行结束的程序，而事实上，不存在一个程序能够判断另一个程序是否与无限循环有染。我们可以来这样设想：假定我们有一个Test程序，此程序把别的测试程序当成输入，我们把它插入另一个程序Paradox（悖论）中，并在Test中使用Paradox函数作为参数（即Paradox（） { … ；Test（Paradox）；…}）。这个Paradox函数的编写思路是这样的，如果Test程序判断Paradox会运行结束，那么Paradox就进入无限循环，如果Test判断Paradox不会结束，则Paradox函数立刻终止。于是Test函数对Paradox函数无效，所以判断函数是否会终止的程序不存在。

计算机不能解一些问题并不是计算机的弱点，因为停机问题本质上是不可解的，不可能建造出一个解停机问题的机器。通用计算机无法完成的计算，无论什么东西同样无法胜任。

图灵机的定义与举例：

接下来我们给出图灵机模型的一个严格的形式定义：

一个图灵机是一个七元组（Q，∑，σ，δ，q₀，q_accept，q_reject），其中Q，∑，σ都是有穷集合。

Q是状态集；

∑是输入字母表，不包括特殊空白符号；

σ是带字母表，其中包括∑与空白符号；

δ：Q×σ→Q×σ×（L，R）是转移函数；

q₀∈Q是起始状态；

q_accept∈Q是接收状态；

q_reject∈Q是拒绝状态；

下面是图灵机的图示：

http://s10/middle/64ac3ab147ecba6df5699&690

从上述形式定义可以看出模型的关键在于有穷控制器中的状态转换函数，根据图灵的通用计算理论，这个转换函数是灵活可变的（对应于通用图灵机），当然也可以使单一的（对应于专用图灵机，即便如此，它的能力也强于有限状态机，因为图灵机是可以接受0级语言的），不过这并非图灵提出图灵机的意义所在。

下面我们来比较有限状态机与通用图灵机的区别所在：

1、 图灵机既能读又能写；

2、 带子是无限长的（可以无限存储，结合读写头既能左移又能右移的特点，当然就可以解决判断输入的0与1个数谁多的问题），而且带子上不但可以写入数据，还可以写入实现某一具体功能的；

3、 进入拒绝和接收状态立即停机；

同有限状态机一样，我们构造一个图灵机来实现一个简单的功能。

目标：利用二进制来设计一个专门计算“x+1”的图灵机，要求计算完成时，读写头要回归原位。

状态集合K：

{start，add，carry，noncarry，overflow，return，halt}；

字母表∑：{0，1，*}；

初始状态s：start；

停机状态集合H：{halt}；

规则集合δ：

 
http://s4/middle/64ac3ab147ecba639f0f3&690