另有一组有穷个形如下式的规则：                                          

s_i,q_j ® s_k,q_l,d. 其中 d=H,L或R.

图灵机器这样执行：开始时，在图灵机带子的一串格子上放上由符号（除b外）组成的初始字，其余格子均放置空格符号b。读写头处于初始状态q₁ ，并指向初始字的第一个格子。然后如下执行。如果所指的符号是s_i, 读头的状态是q_j，刚好是某规则的左端，则按照该规则做动作：在所指格子上写符号s_k，读头变换状态为q_l，根据d的值（d=H,L或R）读头位置保持不动(H)，左移(L)或右移(R)一格。

上一步做完后，如果所指的符号和读头的状态刚好又是规则组中某规则的左端，则图灵机器按此规则继续执行。余次类推，直到所指的符号和读头的状态不能同所有规则的左端匹配时，图灵机停机，执行终止。一般将执行终止时带子上的字作为相对于初始字的计算结果。

我用Java编了一个图灵机的模拟软件，在讲座时可以演示图灵机的执行过程。如果阅读此文就只好自己做做练习，来体验图灵机的执行了。例如下面就是一个把二进制数展开成同等数量的1的图灵机。例如，初始字是10，结果就是11，初始字是101，结果就是11111等,…。此图灵机的符号集={b,0,1}，状态集={q1,…, q7,St,Er}，规则集合是：

b,q1®b,q7,L;  b,q2®b,q3,R;  b,q3®1,q4,L;  b,q4®b,q5,L;

b,q5®b,Er,H;  b,q6®b,q1,R;  b,q7®b,St,H;

0,q1®0,q1,R;  0,q2®0,q2,R;  0,q3®0,q3,R;  0,q4®0,q4,L;

0,q5®1,q5,L;  0,q6®0,q6,L;  0,q7®b,q7,L;

1,q1®1,q2,R;  1,q2®1,q2,R;  1,q3®1,q3,R;  1,q4®1,q4,L;

1,q5®0,q6,L;  1,q6®1,q6,L;  1,q7®1,Er,H;

如果执行中每次只可能有一个规则匹配，也就是说所有规则的左端都不完全相同，图灵机的执行是唯一确定的，称这样的机器为确定的图灵机。反之，有两个或更多的规则的左端完全相同时，图灵机的执行就不是唯一确定的，称这样的机器为非确定的图灵机。

图灵的伟大贡献不仅是提出了图灵机器的概念，更重要的是还提出了通用图灵机的概念。我们把一个这样构造的图灵机T，称为通用图灵机:　对任给的图灵机A，只要把它(A)的规则和初始字，并列起来作为通用图灵机T的初始字，让通用图灵机T运行，运行结果就是图灵机A的运行结果。而正是这个思想奠定了10年后通用电子计算机出现的理论基础。

                                                （未完待续）