的桂冠。

在图灵看来，

这台机器只用保留一些最简单的指令，

一个复

< br>杂的工作只用把它分解为这几个最简单的操作就可以实现了，

在

< br>当时他能够具有这样的思想确实是很了不起的。

图灵机 的产生一方面奠定了现代数字计算机的基础

（要知道

后来冯•诺 依曼就是根据图灵的设想才设计出第一台计算机的）

。

另一方面 ，

根据图灵机这一基本简洁的概念，

我们还可以看到可

计算的极限是什么。

也就是说实际上计算机的本领从原则上讲是

有限制的。

请注意，

这里说到计算机的极限并不 是说它不能吃饭、

扫地等硬件方面的极限，

而是仅仅就从信息处 理这个角度，

计算

机也仍然存在着极限。这就是图灵机的停机问 题。

二．

图灵机原理及分析

图灵的基本思想是 用机器来模拟人们用纸笔进行数学运算

的过程，他把这样的过程看作下列两种简单的动作 ：

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

２）

把

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

而在每个阶段，人要决定下一步的动作，依赖于

(a)

此人

当前所关注的纸上某个位置的符号和

( b)

此人当前思维的状态。

为了模拟人的这种运算过程，

图灵构造出一台假想的机器，

该机

器由以下 几个部分组成：

一条无限长的纸带。

纸带被划分为一个接一个的小格子，

每

个格子上包含一个来自有限字母表的符号，

字母表中有一个特殊

的符号

表示空白。纸带上的格子从左到右依此被编号为

0, 1,

2, ...

，纸带的右端可以无限伸展。

一个读 写头。

该读写头可以在纸带上左右移动，

它能读出当

< br>一个状态寄存器。

它用来保存图灵机当前所处的状态。

图 灵

机的所有可能状态的数目是有限的，

并且有一个特殊的状态，

称

为停机状态。

一套控制规则。

它根据当前机器所处的状态以及当前读写头

所指的格子上的符号来确定读写头下一步的动作，

并改变状态寄

存器的值，令机器进入一个新的状态。

这个机器的每一部分都 是有限的，

但它有一个潜在的无限长

的纸带，

< br>因此这种机器只是一个理想的设备。

图灵认为这样的一

台 机器就能模拟人类所能进行的任何计算过程

下面我们用另一种思想来理解图灵机：

注：以下内容来自百度文库：

小虫的比喻：

我们不妨考虑这样

一个问题

.

假设一个小虫在地上