另有一组有穷个形如下式的规则:
si,qj ® sk,ql,d. 其中 d=H,L或R.
图灵机器这样执行:开始时,在图灵机带子的一串格子上放上由符号(除b外)组成的初始字,其余格子均放置空格符号b。读写头处于初始状态q1 ,并指向初始字的第一个格子。然后如下执行。如果所指的符号是si, 读头的状态是qj,刚好是某规则的左端,则按照该规则做动作:在所指格子上写符号sk,读头变换状态为ql,根据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年后通用电子计算机出现的理论基础。
(未完待续)