一个能够让你明白图灵机的例子

姜咏江

    读了图灵的文章，根据我的理解，设计个逻辑运算的例子：

   设M=（Q，Σ，Γ，δ，q0,qaccept,qreject）其中Σ＝｛0，1，+，*，！｝，

Γ＝｛□，0，1，+，*，！｝。Γ的书写格式为“！x”“+xy”“*xy”并要以“□□□□”间隔。

    表格中的L、R表示读写头左移一格或右移一格。每个字符占用一格。运算结束以后再读入一个空格，让读写头晃一下，再进入开始状态做下面的运算。

   从表 2‑1我们可以看到，在此表中图灵机的状态集合

Q={x,y,z,z0,z1,f,f0,f1,end,erro}，其中x是初始状态，end是运算结束状态，erro是停机拒绝状态。

    表中symbol是读写头每次读入的内容，它与m-config 一起构成了定义域元素，而经过操作行为Behaviour，其中包括移动读写头和输出（打印）数据，而转化为最终状态Final m-config。这一前一后的状态转换，形成了有序的运算操作，最终在不出现错误的情况下，得到运算的结果。

   注意，operations 一栏p0，p1，p*分别表示读写头往当前格子上写0、1和*字符，移动R或L与它们排在一起，表明了动作同时，也标明了先后顺序。

表 2‑1  图灵机状态变化表

 从从表 2‑1我们不难看出，影响下一个状态出现的每一个过程都与原来的状态

Q（m-config）和输入数据Symbol（属于集合Γ中元素）有关。经过operations操作，才到达了新的状态Q'（Final m-config）。显然这种确定的映射可以用Q'=δ(q,γ）来表示，q∈Q，γ∈Γ。表 2‑1就是具体的映射Q'=δ(q,γ）。

    图灵机的qaccept在这个例子中就是end，而qrejet就是erro。

    特别要说明，当我们将Q、Σ和Γ中的元素也都用二进制数表示的时候，Q'=δ(q,γ）就是函数。

    下面添加详细的解释。

例如，我们要计算逻辑值1和0的与运算和或运算结果。先可以在带子上安格写入：

                            □□□□*10□□□□+10□□□□

这里要用4个空格区分两组运算，这是设计的规定。初始化时读写头定在最左边的位置。开始状态是x，与读写头读入的一个空格“□”组成一组“x和□”，向右在operations栏有R，这是让读写头右移一格后，进入了下一个状态，从表上看，这种情况的下一个状态仍然是x。这样连续进行4步，在第5步，读写头将读到“*”，根据表中“x和*”状态的规定，现将读写头右移，并决定出状态“z”。第6步要到左边状态栏找到“z”，这时读写头会读出“1”。依据“z 和1”向右见到“R”，这是将读写头右移一位的控制，并在下一个状态栏找到状态z1。回头再到左边栏找到“z1”，这时读写头将读到“0”。第7步，要依据“z1和0”一行的操作“R，P0”现将读写头右移一位，然后在空格位置写上“0”，并进入到“end”状态。第8步，左面的“end”状态若有读写头读进空格，则依“end和□”行，见操作项是“R,L,R”，这是晃动读写头，表示运算结束，前面写出的“0”就是1和0做与运算的结果。如果读写头读入的是错误的数据，会连续打印出2个星号“**”表明带子上的输入有误，那么就会进入“erro”状态，拒绝继续执行，同时停机。

不是错误的情况，仍然可以让读写头继续读。因为得出结果之后由“end和□”状态确定的下一个状态是x，因而又回到了开始运行的情况。连续地3次读到空格后，就可以读到“+”，按着与运算的查找方法，就可以最后得出1和0做或运算的结果了。

2014－11－3