理解图灵机

姜咏江

图灵机用形式语言定义从维基百科摘抄如下：

Following Hopcroft and Ullman (1979, p. 148), a (one-tape) Turing machine can be formally defined as a 7-tuple

where

• Q  is a finite, non-empty set of states

• Γ  is a finite, non-empty set of tape alphabet symbols

• b∈Γ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)

• ∑  is the set of input symbols

• q0 is the initial state

• F is the set of final or accepting states.

• 

• is a partial function called the transition function, where L is left shift, R is right shift.

Anything that operates according to these specifications is a Turing machine.

按照现代计算机的观点，我理解如下：

图灵机M是一个七元组M=｛Q，Γ，b，Σ，δ，q0，F｝其中

1.  Q是一个非空有限状态集；

2.  Γ是可输入到带子上非空有限字符集；

3.  空格b是带子上计算步骤的间隔符；

4.  Σ是不包括空格的输入符号集；

5.  δ是不包括F的Q×Γ空间到Q×Γ×{L,R｝的函数，称为转换函数。L是左移，R是右移；

6.   q0是初始状态；

7.   F是输入或结束状态。

任何机器符合以上七个条件，就是一个图灵机。

结合现代计算机，对七大条件的理解十分重要。

第一，Q不能理解成程序的指令集，而应理解成解决问题的函数查找变化表。

第二，Γ是数据集，也就是往带子上写的数据。图灵机带子上数据和问题是在接收状态下用特殊方法写上去的，在运行状态可以由读写头改写。

第三，空格做为带子上单词或数据的分隔符，故不应包含在输入字符集中。

第四，转换函数δ是具有函数特性的规定。也就是每次从带子上读到一串问题和数据，都会转换成函数问题，解决的方法就是查表（表是函数的一种表达方式）。通过状态表可以找到问题的答案，然后将答案写入带子上的问题描述部分。读的过程，读写头要从左向右逐步移动，以便并实现理解问题的和数据，建立该问题的状态表，这些都是预先用表函数的方法建立好的。这一部分不是图灵机自身可以完成的事，是人们的思维结晶，是一种问题的解题方法。因而一切可解的问题的解法都在其中。

对于状态转换函数的理解是理解图灵机的关键。我们可以将图灵机运行解释以下：

（1）输入状态是接收问题及数据的过程，也就是要把问题用Σ中的符号顺序写到带子上，不论单词或数据之间要用空格分开，才能辨认和理解。比如在带子上写上“求3加2的和”，这是中文描述，数学上可以写成3+2＝。这一过程图灵机自己不能做，所以要有输入状态。这一状态图灵机不工作。

（2）图灵机要有开始工作的问题，这叫初始化状态q0。问题已经写到带子上了，那么图灵机的读写头位置一定要放在问题描述开始的地方。假如问题是从左向右写的，那么读写头就要从左向右逐个格子阅读，理解问题的本质。譬如读入“3”它就会在状态表中找到能够放置数的地方，读到“+”，它就要找到加法表，再读到“2”，它就应该在表中找到3+2＝5。查表的过程是图灵机自己完成的吗？实际还不是，是“他”完成的。他完成之后，将结果5通过读写头写到现在读写头的位置，因为问题已经解决了，覆盖掉问题在带子上的符号，不影响问题的解决。

（3）如果带子上写的问题很复杂，或者有好几个问题，那么读写头当然要移动。向右去读新的问题，向左往往是去处理尚未完全解决的问题。不要将左右移动读写头只是一个格子移动就要去查状态表，有时候要连续移动若干个格子，不进行读写。比如，重新解决前面描述的一些问题等，这要重新去读。

（4）停机状态是必须的。F除了是前面说的需要往带子上写问题之外，当问题已经完成之后，做为终结形式用停机状态最好。

• 在图灵机理解当中，第5条

  

  is a partial function called the transition function, where L is left shift, R is right shift.

Anything that operates according to these specifications is a Turing machine.

一般要理解清楚partial function，这是在不完全论域上的函数，function在这里理解成一般变元论域上的不完全映射比较更好。

如何构造转换函数，图灵机并没有解决。到了现代计算机的时代，从冯.诺依曼之后，这些问题才可以用机器运行实现。

2014-10-24