图灵机模型与计算机

图灵机模型与计算机（一）

一、图灵机的构成

1、一条无限长的纸带（tape）。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字幕的符号，字母表中有一个特殊的符号，就是一个空格，它表示空白。纸带上的格子从左到右依次被编号为0，1，2...，右端无限延伸。
2、一个读写头（head）可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
3、一套控制规则（table），它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
4、一个状态寄存器，用来保存图灵机当前所处的状态。图灵机的所有可能的状态的数目是有限的，并且有一个特殊的状态，成为“停机状态”。

二、图灵机的正定式定义

一台图灵机是一个七元组 $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$ ，其中 $Q, \Sigma, \Gamma$ 都是有限集合，且满足

$Q$ 是状态集合；
$\Sigma$ 是输入字母表，其中不包含特殊的空白符 $\square$ ；
$b \in \Gamma$ 为空白符；
$\Gamma$ 是带字母表，其中 $\square \in \Gamma$ 且 $\Sigma \subset \Gamma$ ；
$\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ 是转移函数，其中 $L, R$ 表示读写头是向左移还是向右移；
$q_0 \in Q$ 是起始状态；
$q_{accept} \in Q$ 是接受状态。 $q_{reject}\in Q$ 是拒绝状态，且 $q_{reject}\neq q_{accept}$ 。

图灵机 $M=(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$ 将以如下方式运作：

开始的时候将输入符号串 $\omega=\omega_0\omega_1\ldots\omega_{n-1} \in \Sigma^*$ 从左到右依此填在纸带的第 $0, 1, \ldots , n-1$ 号格子上，其他格子保持空白（即填以空白符 $\square$ )。 $M$ 的读写头指向第0号格子， $M$ 处于状态 $q_0$ 。机器开始运行后，按照转移函数 $\delta$ 所描述的规则进行计算。例如，若当前机器的状态为 $q$ ，读写头所指的格子中的符号为 $x$ ，设 $\delta(q,x) =(q\', x\', L)$ ，则机器进入新状态 $q\'$ ，将读写头所指的格子中的符号改为 $x\'$ ，然后将读写头向左移动一个格子。若在某一时刻，读写头所指的是第0号格子，但根据转移函数它下一步将继续向左移，这时它停在原地不动。换句话说，读写头始终不移出纸带的左边界。若在某个时刻 $M$ 根据转移函数进入了状态 $q_{accept}$ ，则它立刻停机并接受输入的字符串；若在某个时刻 $M$ 根据转移函数进入了状态 $q_{reject}$ ，则它立刻停机并拒绝输入的字符串。

注意，转移函数 $\delta$ 是一个部分函数，换句话说对于某些 $q$ , $x$ ， $\delta(q,x)$ 可能没有定义，如果在运行中遇到下一个操作没有定义的情况，机器将立刻停机。

三、图灵机解决问题示例

设 $M=(\{0,1,10,11\}, \{0,1\}, \{0,1,\square\}, \delta, 0, , )$ 和 $\delta:\{0,1,10,11\}\times\{0,1\}\to\{0,1,10,11\}\times\{0,1\}\times\{R,L,E,S\}$ . 比如做一个以1的个数表示数值的加法运算，在磁带上的数据是0000001110110000，就是3+2的意思。程序 $\delta$ 如下：

0,0 -> 0,0R

0,1 -> 1,1R

1,0 -> 10,1R

1,1 -> 1,1R

10,0 -> 11,0L

10,1 -> 10,1R

11,0 -> E

11,1 -> 0,0S

第一行程序0,0->0,0R意思就是如果机器读到0，就将其变成0，状态变为0，读写头向右移动一格. R就是向右移动一格，L就是向左移一格，E是错误，S是停机. xx,y -> aa,bb中xx是当前状态, y是当前格子的值, aa是程序下一步的状态, b是当前格的修改值。

虽然这里给出与上面不同形式的定义，但两者是等价的，这里的定义能完成的工作并不比上面的定义多。

步数	状态	磁带	步数	状态	磁带
1	0	0000001110110000	9	1	0000001110110000
2	0	0000001110110000	10	1	0000001110110000
3	0	0000001110110000	11	10	0000001111110000
4	0	0000001110110000	12	10	0000001111110000
5	0	0000001110110000	13	10	0000001111110000
6	0	0000001110110000	14	11	0000001111110000
7	0	0000001110110000	15	0	0000001111100000（停机）
8	1	0000001110110000	-- 停机 --

四、图灵机计算机

图灵机与计算机是一对一的等价关系。

首先，图灵机能解决的是有算法的问题。图灵机能解决的问题，计算机也能解决；计算机能解决的问题，图灵机也能解决。

图灵机的纸带(储存器）

读写头（运算器）

控制规则（程序）

状态寄存器（计算机的状态）

计算机的内存是有限的，但是加上硬盘，u盘无限个，也就相当于是无限的。一台计算机可以进行的运算比一台图灵机复杂，但是多个图灵机，也可以进行计算机可以进行的复杂的运算。

计算机和图灵机是一脉相承的。

五、图灵停机问题

图灵机根据机器的程序处理初始格局。有的初始格局可能导致停机，有的则导致无限的格局序列。停机问题是：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机。已经证明，这样的算法是不存在的，即停机问题是不可判定的。
停机问题是研究许多不可判定问题的基础，人们往往把一个问题的判定归结为停机问题：“如果问题 A可判定，则停机问题可判定。”从而证明问题 A的不可判定性。停机问题有多种不同的叙述方式和证明方法，它们分别适用于具有不同特征的问题。

秒客网

图灵机模型与计算机

相关文章