软件工程专业导论：图灵机的形式化

图2-2的自动计算机器可归纳为:

(1)一个纸带,分为若干左右相连接的单元。每个单元可以有一个符号,符号是有限的字母或数字(因为字母、数字、其他符号都可以按“0、1”这样的二进制编码表达)的集合。纸带可以无限地左右扩展,即图灵机有足够的纸带单元做计算。

(2)读写头(Head),可以左右移动(一次一个单元),或头不动,纸带左右移动。那么,读写头的移动是否可以按事先设定好的规程(或规律)进行。

(3)指令的有限字母表,参见图2-2中的表。给定机器当前的一个状态和从纸带上读取的符号,然后,查这个表告诉机器下一步(或若干步)做什么(在哪个单元格写什么样的字母)?

上述的若干步骤可以表达为如下的七元组模型:

M=(Q,Γ,b,Σ,δ,q0,F)

式中,Q 是一个有限的、非空状态集合;

Γ 是一个有限的、非空纸带字母符号集合;

b∈Γ 是空符号(唯一的空符号,在计算中可用);

Σ⊆Γ\{b}是输入符号集合,即运行出现在初始纸带内容上的符号集合;

q0∈Q 是初始状态;

F⊆Q 是最终状态或可测试状态结果的集合。

δ:(Q\F)×Γ→Q×Γ×{L,R}是一个偏序函数,称为迁移函数,这里,L 是左移,R 是右移。位置不变称为不移动(no shift,记为N)。如果当前的状态和当前的纸带没有定义δ时,那么机器停机。

例如:具有三个状态的七元组的图灵机如下:(www.xing528.com)

Q={A,B,C,HALT}

式中,Γ={0,1};

b=0(空符号);

Σ={1}(输入符号);

q0=A(初始状态);

F={HALT}(最终状态);

δ如表2-2(迁移函数)所示。

表2-2 一个状态迁移函数δ

表2-2就是程序,用一个机器查表2-2,由此,机器从当前状态迁移到新的状态,就是程序的自动执行。这样的机器就是图灵计算机器。

问题是如何制造出可以自动查表和状态迁移的机器,或者有更好的形式完成类似的工作。

实际上,按图2-1的设计方案,可以制造出计算机器,但是过于复杂。这促使人们要想出更好的设计方案。