图灵机状态转移函数为什么是部分函数？

姜咏江

图灵机是神秘的机器，能够很通俗地将它解释清楚文章很难找到。为了透彻地理解图灵，我们不妨先对图灵机定义做一点详细的研究。

关于图灵机的数学定义一般介绍如下：

一台图灵机M是一个七元组，{Q，Σ，Γ，δ，q0,qaccept,qreject}，其中 Q，Σ，Γ 都是有限集合，且满足：

（1）Q 是有限状态集合；

（2）Σ是输入字母表，其中不包含特殊的空白符 □；

（3）Γ 是带子上字母表，其中 □∈Γ且ΣΓ ；

（4）δ：Q×Γ→Q×Γ×{L,R}是转移函数，其中L,R 表示读写头是向左移还是向右移；

（5）q0∈Q是起始状态；

（6）qaccept是接受状态；

（7）qreject是拒绝接收状态，且qreject≠qaccept。

这是啥意思？定义的（2）和（3）条比较好理解，Σ可以理解成英文的字母符号表，最简单的可以将它理解成Σ=｛0,1｝。Γ是写在带子上的字母表，为了区分不同的连续表达的意思，用空格来区分这是书写的常规。这里说ΣΓ 是因为集合Γ比集合Σ多了一个空格字符□。我们用最简单的情况考虑，理解Γ=｛0,1,□｝。

用一定位数的二进制数可以表达语言文字。例如，8位的西文ascll编码表，或者16位的unicode编码表。16位的汉字编码表等。将Γ带子上的“格子”是理解成单独的0和1，还是理解成由一定位数的二进制编码组织的数据？这是理解好图灵机的一个关键问题。笔者认为，将带子上的格子理解成能写入固定位数的二进制数较妥。

定义中的（5）是任何机器运行所必需的条件。q0∈Q是说q0也是一个状态，但究竟是怎样的一种状态？却是留下了进一步想象的空间。

定义（6）和（7）的理解是多样的。接受状态和拒绝状态是指什么？是指转移函数接受读写头读出的字符还是拒绝？

定义中最难理解的是δ：Q×Γ→Q×Γ×{L,R}这个转移函数。关于转移函数的讨论，我们用具体的问题来看一下。

表 1是我们设计的一个二进制两位数乘法运算的图灵机转移函数。Σ＝｛00，01，10，11｝。不考虑空格和怎样打印输出，实际这个转移函数就是δ：Q×Σ→Q×Σ。左面Σ是读入的二进制数，右面的Σ应该是输出两位的二进制数。

从表 1的实际乘法运算，我们看到好几项乘法的结果都不在Σ中，此时图灵机就不能够识别，因而会产生拒绝的情况，造成停机。

本来两位二进制数乘积应是｛00，01，10，11，100，110，1001｝这是两位数的乘法运算值域，但Σ中不包含100、110、1001，也就是说函数不构成满射，所以才叫部分函数。

表中能够返回q₀的情况就叫接受状态qaccept。Q={q₀,q₁,q₂,q₃,q₄,qaccept,}。定义中的qreject实际上应不属于Q，不然就造成了悖论。

表1  两位数乘法运算图灵机转移函数

2014-11-8