• 7. 循环与无穷性
  • 学习目标
  • 7.1 图灵机
    • 7.1.1 扩展示例: 识别回文的图灵机
    • 7.1.2 图灵机: 形式化定义
    • 7.1.3 可计算函数
    • 7.1.4 无限循环与偏函数
  • 7.2 作为编程语言的图灵机
    • 7.2.1 NAND-TM 编程语言
    • 7.2.2 先睹为快: NAND-TM 与图灵机
    • 7.2.3 示例
  • 7.3 图灵机与 NAND-TM 程序的等价性
    • 7.3.1 再谈规范与实现
  • 7.4 NAND-TM 语法糖
    • 7.4.1 “GOTO” 与内层循环
  • 7.5 均匀性以及 NAND 与 NAND-TM 的比较 (讨论)
  • 7.6 习题
  • 7.7 参考文献说明

7. 循环与无穷性

学习目标

• 学习 图灵机 的模型, 其可以计算 任意长度输入 的函数.
• 通过 NAND-TM 程序了解图灵机的程序语言描述, 其在 NAND-CIRC 的基础上增加了 循环 和 数组.
• 了解图灵机与 NAND-TM 程序的一些基本语法糖和等价的变体.

正如 第六章 的引言所述, 算法是 “以有限回答无穷”. 为了表示一个算法, 我们需要写下一组有限多的指令, 其能够计算任意长度的输入.

我们需要以下组件来描述和执行一个算法 (见 图 7.1):

• 一组有限多的用于执行的指令.
• 在执行过程中被使用的一些 “局部变量” 或有限状态.
• 一个潜在的无界工作内存, 用于存储输入和我们可能需要的其他值.
• 当内存无界时, 我们每一步只能读写其中的有限部分, 我们需要一种方式来 寻址 我们想要读写的内存部分.
• 如果我们只有有限多的指令, 但我们的输入可以是任意长的, 我们将需要 重复 指令 (即 循环 回去). 我们需要一种机制来决定何时循环, 何时停止.

7.1 图灵机

所有计算模型的 “鼻祖” 是 图灵机. Alan Turing 于 1936 年定义了图灵机, 试图形式化地刻画遵循一组明确定义的规则 (例如标准加法或乘法算法) 的人类 “计算员” (见 图 7.4) 所能计算的全部函数.

Turing 设想, 这样的人可以按需取用任意多的 “草稿纸”. 为简单起见, 可以把这张草稿纸想成一条一维的方格纸 (通常称为 磁带). 纸被划分成若干 “单元” , 每个 “单元” 可以容纳一个符号 (例如一个数字或字母, 更一般地说, 是某个有限 字母表 中的元素). 在任意时刻, 这个人都可以读取或写入纸上的一个单元.他可以根据该单元的内容更新自己有限的思维状态, 并且/或者移动到当前单元紧邻的左侧或右侧单元.

Turing 用一台维持 $k$ 种状态之一的 “机器” 来模拟这种计算. 在任意时刻, 机器从它的 “工作磁带” 上读取有限字母表 $\Sigma$ 中的一个符号, 并据此更新自身状态、写入磁带, 还可能移动到相邻单元(见 图 7.7). 为了用这台机器计算函数 $F,$ 我们用输入 $x\in \{0,1{\}}^{\ast }$ 初始化磁带, 目标是确保计算结束时磁带包含值 $F(x).$ 具体而言, 具有 $k$ 个状态和字母表 $\Sigma$ 的图灵机 $M$ 在输入 $x\in \{0,1{\}}^{\ast }$ 上的计算过程如下:

• 最初, 机器处于状态 $0$ (称为“初始状态“), 磁带被初始化为 $▹,x_0,\dots ,x_{n-1},\varnothing ,\varnothing ,\dots .$ 我们用符号 $▹$ 表示磁带的起点, 用符号 $\varnothing$ 表示空白单元.我们始终假定字母表 $\Sigma$ 是 $\{▹,\varnothing ,0,1\}$ 的超集 (可能是真超集).
• 将机器所指向的位置 $i$ 设为 $0.$
• 在每一步中, 机器读取磁带第 $i$ 个位置上的符号 $\sigma =T[i].$机器根据该符号及其状态 $s$ 决定:
  • 在磁带上写入什么符号 ${\sigma }^{\prime };$ \
  • 向左 (Left, 即 $i\leftarrow i-1)$ 移动、向右 (Right, 即 $i\leftarrow i+1)$ 移动、停留 (Stay) 在原处, 还是停机 (Halt) ;
  • 新状态 $s\in [k]$ 是什么.
• 图灵机所遵循的规则集合称为它的 转移函数.
• 机器停机时, 从磁带起点开始读取, 直到第一个包含 $\varnothing$ 符号的位置, 并依次输出其中所有的 $0$ 和 $1$ 符号, 由此得到的二进制串即为机器的输出; 若开头存在 $▹$ 符号, 则将其丢弃, 末尾的 $\varnothing$ 符号同样丢弃.

7.1.1 扩展示例: 识别回文的图灵机

令 $PAL$ (表示 回文) 为如下函数: 对于输入 $x\in \{0,1{\}}^{\ast },$ 当且仅当 $x$ 是一个 (长度为偶数的) 回文 时输出 $1;$ 这里回文是指存在某个 $n\in \mathbb{N}$ 和 $w\in \{0,1{\}}^n,$ 使得 $x=w_0\cdots w_{n-1}{w}_{n-1}{w}_{n-2}\cdots w_0.$

下面给出一台计算 $PAL$ 的图灵机 $M.$为了描述 $M,$ 我们需要指定 (i) $M$ 的磁带字母表 $\Sigma ,$ 它至少应包含符号 $0$、$1$、$▹$ 和 $\varnothing ;$ 以及 (ii) $M$ 的 转移函数, 它决定 $M$ 处于特定状态并读到给定符号时所采取的动作.

在本例中, $M$ 使用字母表 $\{0,1,▹,\varnothing ,\times \},$ 并具有 $k=11$ 个状态. 尽管这些状态只是从 $0$ 到 $k-1$ 的数字, 但为方便起见, 我们给它们加上如下标签:

下面用文字描述图灵机 $M$ 的运行过程:

• $M$ 从 START 状态开始向右移动, 寻找第一个为 $0$ 或 $1$ 的符号.如果尚未遇到这样的符号便先遇到 $\varnothing ,$ 它就转入下文所述的 OUTPUT_1 状态.

• 一旦 $M$ 找到这样的符号 $b\in \{0,1\},$ 它便写入 $\times$ 符号, 以此从磁带上删除 $b;$ 随后进入 RIGHT_$b$ 状态并开始向右移动, 直到遇到第一个 $\varnothing$ 或 $\times$ 符号.

• $M$ 找到该符号后, 根据此前处于 RIGHT_0 还是 RIGHT_1 状态, 分别转入 LOOK_FOR_0 或 LOOK_FOR_1 状态, 并向左移动一步.

• 在 LOOK_FOR_$b$ 状态下, $M$ 检查磁带上的值是否为 $b.$ 如果是, $M$ 就把该值改为 $\times$ 以将其删除, 并转入 RETURN 状态; 否则, 它转入 OUTPUT_0 状态.

• RETURN 状态表示 $M$ 返回起点. 具体来说, $M$ 不断向左移动, 直到遇到第一个既不是 $0$ 也不是 $1$ 的符号, 此时它将状态改为 START.

• OUTPUT_$b$ 状态表示 $M$ 最终将输出值 $b.$ 在 OUTPUT_0 和 OUTPUT_1 状态下, $M$ 都会向左移动, 直到遇到 $▹.$ 随后它向右移动一步, 并分别转入 1_AND_BLANK 或 0_AND_BLANK 状态. 在后两个状态中, $M$ 写入相应的值, 向右移动, 然后转入 BLANK_AND_STOP 状态; 在该状态下, 它向磁带写入 $\varnothing$ 并停机.

可以把上述描述转换成一个表格, 列出 $11\cdot 5$ 种状态与符号的组合, 并说明图灵机处于相应状态、读到相应符号时将执行什么操作.这个表格称为图灵机的 转移函数.

7.1.2 图灵机: 形式化定义

图灵机的形式化定义如下:

不要将图灵机 $M$ 的 转移函数 ${\delta }_M$ 与该机器所计算的函数混淆. 转移函数 ${\delta }_M$ 是一个 有限 函数, 有 $k|\Sigma |$ 个输入和 $4k|\Sigma |$ 个输出. (你能看出为什么吗?) 这台机器可以计算一个 无限 函数 $F:$ 它以任意长度的字符串 $x\in \{0,1{\}}^{\ast }$ 为输入, 也可能产生任意长度的字符串作为输出.

在我们的形式化定义中, 机器 $M$ 与其转移函数 ${\delta }_M$ 被视为同一对象, 因为转移函数给出了我们需要知道的关于图灵机的一切信息. 不过, 这种表示方式的选择有一定任意性, 并且建立在如下约定之上: 状态空间始终为数字集合 $\{0,\dots ,k-1\},$ 其中 $0$ 是初始状态. 其他教材采用不同约定, 因此其中图灵机的数学定义表面上可能有所不同. 然而, 这些定义描述的是同一种计算过程, 也具有相同的计算能力. 所以, 尽管存在表面差异, 它们仍然是等价的. 关于 定义 7.1 与 Sipser 等教材中图灵机定义方式的比较, 见第 7.7 节和 Sipser, 1997.

7.1.3 可计算函数

现在我们来给出本书最重要的定义之一: 可计算函数.

把一个函数定义为 “可计算的”, 当且仅当它能由图灵机计算, 这看起来或许有些 “冒进”; 但正如我们将在第 8 章看到的, 定义 7.2 意义下的可计算性, 与几乎所有合理计算模型下的可计算性都等价. 这一论断称为 Church–Turing 论题. (它不同于我们在第 5.6 节讨论的 扩展 Church–Turing 论题; Church–Turing 论题本身得到广泛认同, 并且目前没有任何候选设备能对其构成挑战.)

这里适合提醒读者: 函数 与 程序 并不相同:

$$\text{函数}\ne \text{程序}.$$

图灵机 (或程序) $M$ 可以 计算 某个函数 $F,$ 但 $M$ 并不等同于 $F.$ 特别地, 计算同一个函数的程序可以不止一个. 可计算性是 函数 的性质, 而不是机器的性质.

我们经常会特别关注只输出一个比特的函数 $F:\{0,1{\}}^{\ast }\to \{0,1\}.$ 因此, 我们为这种形式的所有可计算函数构成的集合起一个专门的名字.

7.1.4 无限循环与偏函数

电路/直线程序与图灵机之间有一个关键区别. 对于 NAND-CIRC 程序 $P,$ 只需查看变量 X 和 Y, 我们总能判断 $P$ 有多少个输入和多少个输出. 此外, 我们可以保证: 在任何输入上调用 $P,$ 都会产生 某个 输出.

相比之下, 给定一台图灵机 $M,$ 我们无法预先确定 $M$ 输出的长度. 事实上, 我们甚至不知道它究竟会不会产生输出! 例如, 很容易构造出一台转移函数从不输出 $\mathsf{H},$ 因而永不停机的图灵机.

如果机器 $M$ 在某个输入 $x$ 上无法停机并产生输出, 那么它就不能计算任何全函数 $F,$ 因为显然在输入 $x$ 上, $M$ 无法输出 $F(x).$ 不过, $M$ 仍然可以计算一个 偏函数. ¹

例如, 考虑偏函数 $DIV:$ 输入一对自然数 $(a,b),$ 若 $b>0,$ 则输出 $\lceil a/b\rceil ;$ 否则未定义. 我们可以定义一台在输入 $a,b$ 上计算 $DIV$ 的图灵机 $M:$ 它输出满足 $cb\ge a$ 的第一个 $c=0,1,2,\dots .$如果 $a>0$ 且 $b=0,$ 机器 $M$ 将永不停机, 但这并无问题, 因为 $DIV$ 在这样的输入上未定义.如果 $a=0$ 且 $b=0,$ 机器 $M$ 将输出 $0,$ 这同样没有问题, 因为我们不关心程序在 $DIV$ 未定义的输入上输出什么.形式化地, 偏函数的可计算性定义如下:

注意, 如果 $F$ 是全函数, 那么它在每个 $x\in \{0,1{\}}^{\ast }$ 上都有定义, 因此在这种情况下, 定义 7.4 与 定义 7.2 完全相同.

7.2 作为编程语言的图灵机

“图灵机“这个名称及其“磁带“和“磁头“容易使人联想到实体对象. 与之相对, 我们通常把 程序 看作一段文本. 但我们同样可以把图灵机看作程序. 例如, 考虑第 7.1.1 节中计算函数 $PAL$ 的图灵机 $M,$ 其中 $PAL(x)=1$ 当且仅当 $x$ 是回文. 我们也可以使用如下形式的类 Python 伪代码, 将这台机器描述为 程序:

# 接收一个初始化为如下内容的 Tape 数组:
# [">", x_0 , x_1 , .... , x_(n-1), "∅", "∅", ...]
# 执行结束时, 如果 x 是回文, 则 Tape[1] 等于 1;
# 否则 Tape[1] 等于 0
def PAL(Tape):
    head = 0
    state = 0 # START
    while (state != 12):
        if (state == 0 && Tape[head]=='0'):
            state = 3 # LOOK_FOR_0
            Tape[head] = 'x'
            head += 1 # 向右移动
        if (state==0 && Tape[head]=='1')
            state = 4 # LOOK_FOR_1
            Tape[head] = 'x'
            head += 1 # 向右移动
        ... # 此处还有更多 if 语句

这个程序的具体细节并不重要. 重要的是, 我们可以将图灵机描述为 程序. 此外还要注意, 将图灵机转换为程序时, 磁带 会变成一个 列表 或 数组, 用来保存有限集合 $\Sigma$ 中的值. ² 磁头位置 可以视为一个保存无界大小整数的整数值变量. 状态 是一个 局部寄存器, 它可以保存 $[k]$ 中的某个值, 而 $[k]$ 仅含固定数量的值.

更一般地, 可以把每台图灵机 $M$ 都视为与如下程序等价:

# 接收一个初始化为如下内容的 Tape 数组:
# [">", x_0 , x_1 , .... , x_(n-1), "∅", "∅", ...]
def M(Tape):
    state = 0
    i     = 0 # 保存磁头位置
    while (True):
        # 根据当前状态和磁头所在单元的内容
        # 移动磁头、修改状态并写入磁带
        # 以下内容仅用于展示特定转移函数所对应的程序形式
        if Tape[i]=="0" and state==7: # δ_M(7,"0")=(19,"1","R")
            Tape[i]="1"
            i += 1

            state = 19
        elif Tape[i]==">" and state == 13: # δ_M(13,">")=(15,"0","S")
            Tape[i]="0"
            state = 15
        elif ...
        ...
        elif Tape[i]==">" and state == 29: # δ_M(29,">")=(.,.,"H")
            break # 停机

如果只想使用 布尔 (即取值为 $0$/$1)$ 变量, 那么可以用 $\lceil \log k\rceil$ 个比特编码 state 变量. 类似地, 可以用 $\ell =\lceil \log |\Sigma |\rceil$ 个比特表示字母表 $\Sigma$ 中的每个元素, 因而可以用 $\ell$ 个布尔值数组 Tape0[]、$\dots$、Tape$(\ell -1)$[] 取代取值于 $\Sigma$ 的数组 Tape[].

7.2.1 NAND-TM 编程语言

现在介绍 NAND-TM 编程语言, 它用编程语言的形式体系刻画图灵机的能力. 正如布尔电路与图灵机之间的区别一样, NAND-TM 与 NAND-CIRC 的主要区别在于, NAND-TM 模拟一个 单一的统一算法, 该算法可以计算接受 任意长度输入 的函数. 为此, 我们为 NAND-CIRC 编程语言增加两种结构:

• 循环: NAND-CIRC 是一种 直线编程语言. 一个包含 $s$ 行代码的 NAND-CIRC 程序恰好执行 $s$ 个计算步骤, 因而尤其不可能访问超过 $3s$ 个变量. 循环 使我们能够用长度固定的程序编码一段可能耗费任意长时间的计算所需的指令.

• 数组: 一个包含 $s$ 行代码的 NAND-CIRC 程序至多访问 $3s$ 个变量. 尽管可以在 NAND-CIRC 中使用 Foo_17 或 Bar[22] 这样的变量名, 但它们并不是真正的数组, 因为标识符中的数字是“硬编码“在程序中的常量. NAND-TM 包含真正的数组, 其长度不存在先验上界.

因此, 可以用下面这个非形式化等式来记忆 NAND-TM:

$$\text{NAND-TM}=\text{NAND-CIRC}+\text{loops}+\text{arrays}\text{\hspace{1em}(7.1)}$$

具体来说, NAND-TM 编程语言在 NAND-CIRC 的基础上增加了以下特性 (见 图 7.8):

• 增加一个特殊的 整数值 变量 i. NAND-TM 中的所有其他变量都是 布尔值 变量 (与 NAND-CIRC 相同).

• 除 i 外, NAND-TM 还有两类变量: 标量 和 数组. 标量变量 保存一个比特 (与 NAND-CIRC 相同). 数组变量 保存数量无界的比特. 在计算过程中的任意时刻, 都可以使用 Foo[i] 访问数组变量中由 i 索引的位置. 我们无法访问数组中 i 未指向的位置.

• 我们约定, 数组 的名称总是以大写字母开头, 标量变量 (绝不会用 i 对其进行索引) 的名称以小写字母开头. 因此, Foo 是数组, bar 是标量变量.

• 输入 X 和输出 Y 现在被视为取值为 $0$ 和 $1$ 的 数组. (此外还有两个特殊数组 X_nonblank 和 Y_nonblank, 见下文.)

• 增加一条特殊的 MODANDJUMP 指令. 它以两个布尔变量 $a,b$ 作为输入, 并执行以下操作:

  • 如果 $a=1$ 且 $b=1,$ 则 MODANDJUMP($a,b$) 将 i 递增 $1,$ 并跳转到程序的第一行.
  • 如果 $a=0$ 且 $b=1,$ 则 MODANDJUMP($a,b$) 将 i 递减 $1,$ 并跳转到程序的第一行. (如果 i 已经等于 $0,$ 则保持为 $0.$)
  • 如果 $a=1$ 且 $b=0,$ 则 MODANDJUMP($a,b$) 不修改 i, 直接跳转到程序的第一行.
  • 如果 $a=b=0,$ 则 MODANDJUMP($a,b$) 停止执行程序.

• MODANDJUMP 指令总是出现在 NAND-TM 程序的最后一行, 不会出现在其他任何位置.

默认值. 我们还需要一项约定来处理“默认值“. 图灵机使用特殊符号 $\varnothing$ 表示磁带位置“空白“或“未初始化“. NAND-TM 中没有这样的符号, 所有变量都是 布尔值变量, 取值为 $0$ 或 $1.$ 如果变量或数组位置尚未初始化为其他值, 其默认值均为 $0.$ 为了记录数组中的 $0$ 表示真正的零还是未初始化的单元, 程序员可以为数组 Foo 添加一个“伴随数组“ Foo_nonblank, 并在第 i 个位置初始化时将 Foo_nonblank[i] 设为 $1.$ 特别地, 我们将对输入数组 X 和输出数组 Y 使用这一约定. NAND-TM 程序有 四个 特殊数组: X、X_nonblank、Y 和 Y_nonblank. 在长度为 $n$ 的输入 $x\in \{0,1{\}}^{\ast }$ 上执行 NAND-TM 程序时, 数组 X 的前 $n$ 个单元被初始化为 $x_0,\dots ,x_{n-1},$ 数组 X_nonblank 的前 $n$ 个单元被初始化为 $1.$ (所有未初始化单元的默认值均为 $0.$) NAND-TM 程序的输出是字符串 Y[$0$]、$\dots$、Y[$m-1$], 其中 $m$ 是使 Y_nonblank[$m$]$=0$ 成立的最小整数. 调用 NAND-TM 程序时, X 和 X_nonblank 已被初始化并包含输入, 程序通过写入 Y 和 Y_nonblank 产生输出.

形式化地, NAND-TM 程序的定义如下:

7.2.2 先睹为快: NAND-TM 与图灵机

顾名思义, NAND-TM 程序是以编程语言形式对图灵机的直接实现. 我们将在下文证明两者的等价性, 但现在已经可以看出图灵机与 NAND-TM 程序的各个组成部分如何相互对应:

7.2.3 示例

下面给出一些 NAND-TM 程序示例.

carry = IF(started,carry,one(started))
started = one(started)
Y[i] = XOR(X[i],carry)
carry = AND(X[i],carry)
Y_nonblank[i] = one(started)
MODANDJUMP(X_nonblank[i],X_nonblank[i])

temp_0 = NAND(started,started)
temp_1 = NAND(started,temp_0)
temp_2 = NAND(started,started)
temp_3 = NAND(temp_1,temp_2)
temp_4 = NAND(carry,started)
carry = NAND(temp_3,temp_4)
temp_6 = NAND(started,started)
started = NAND(started,temp_6)
temp_8 = NAND(X[i],carry)
temp_9 = NAND(X[i],temp_8)
temp_10 = NAND(carry,temp_8)
Y[i] = NAND(temp_9,temp_10)
temp_12 = NAND(X[i],carry)
carry = NAND(temp_12,temp_12)
temp_14 = NAND(started,started)
Y_nonblank[i] = NAND(started,temp_14)
MODANDJUMP(X_nonblank[i],X_nonblank[i])

temp_0 = NAND(X[0],X[0])
Y_nonblank[0] = NAND(X[0],temp_0)
temp_2 = NAND(X[i],Y[0])
temp_3 = NAND(X[i],temp_2)
temp_4 = NAND(Y[0],temp_2)
Y[0] = NAND(temp_3,temp_4)
MODANDJUMP(X_nonblank[i],X_nonblank[i])

7.3 图灵机与 NAND-TM 程序的等价性

根据前面的讨论, 图灵机最终被证明与 NAND-TM 程序等价或许并不令人惊讶. 事实上, 我们设计 NAND-TM 语言时就有意使其具备这一性质. 尽管如此, 这仍然是一个重要结论, 也是本书将介绍的许多同类等价性结论中的第一个.

7.3.1 再谈规范与实现

理解 NAND-TM 程序和图灵机的定义后, 定理 7.1 就显而易见了. 事实上, 与其说 NAND-TM 程序是不同于图灵机的模型, 不如说它只是用编程语言记法重新表述了同一个模型. 可以把图灵机与 NAND-TM 程序之间的区别, 看作使用十进制记法或二进制记法表示同一个数的区别. 相比之下, 函数 $F$ 与计算 $F$ 的图灵机之间存在深刻得多的区别: 这就像方程 $x^2+x=12$ 与该方程的解 $3$ 之间的区别. 因此, 尽管我们会特别注意区分 函数 与 程序 或 机器, 却经常把后两个概念视为同一概念. 我们会自由地把算法描述为图灵机或 NAND-TM 程序 (以及第 8 章及以后将介绍的其他等价计算模型).

7.4 NAND-TM 语法糖

正如第 4 章对 NAND-CIRC 所做的那样, 可以使用“语法糖“使 NAND-TM 程序更容易编写. 首先, 可以使用 NAND-CIRC 的全部语法糖, 例如宏定义和条件语句 (即 if/then). 不仅如此, 我们还可以实现以下特性:

• 内层循环, 例如许多编程语言中常见的 while 和 for 操作.

• 多个 索引变量 (例如不只有 i, 还可以添加 j、k 等).

• 多维 数组 (例如 Foo[i][j]、Bar[i][j][k] 等).

在所有这些情形以及许多其他情形中, 都可以把新特性实现为标准 NAND-TM 之上的“语法糖“. 这意味着, 加入该特性的 NAND-TM 所能计算的函数集合, 与标准 NAND-TM 所能计算的函数集合相同. 类似地, 可以证明具有多条磁带或多维磁带的图灵机所能计算的函数集合, 与标准图灵机所能计算的函数集合相同.

7.4.1 “GOTO” 与内层循环

我们可以实现比简单的 MODANDJUMP 更高级的 循环结构. 例如, 可以实现 GOTO. 一条 GOTO 语句表示在执行过程中跳转到特定代码行. 例如, 假设有如下形式的代码:

"start":  do foo
   GOTO("end")
"skip": do bar
"end": do blah

程序将只执行 foo 和 blah, 因为执行到 GOTO("end") 时, 它会跳转到标有 "end" 的代码行. 在 NAND-TM 中, 可以使用条件语句实现 GOTO 的效果. 在下面的代码中, 假设有一个变量 pc, 它可以取某个恒定长度的字符串作为值. 这可以用有限多个布尔变量 pc_0、pc_1、$\dots$、pc_$k-1$ 编码. 因此, 下文写出 pc = "label" 时, 实际含义类似于 pc_0 = 0、pc_1 = 1、$\dots$ (其中比特 $0,1,\dots$ 对应于将有限字符串 "label" 编码为长度为 $k$ 的字符串). 我们还假设可以使用条件语句 (即 if 语句), 它可以像 NAND-CIRC 中那样用语法糖模拟.

为了模拟 GOTO 语句, 首先把如下形式的程序 P

do foo
do bar
do blah

修改为如下形式 (对 if 使用语法糖):

pc = "line1"
if (pc=="line1"):
    do foo
    pc = "line2"
if (pc=="line2"):
    do bar
    pc = "line3"
if (pc=="line3"):
    do blah

这两个程序执行相同的操作. 变量 pc 对应“程序计数器“, 用于告诉程序接下来执行哪一行. 可以看出, 如果想模拟 GOTO("line3"), 只需将指令 pc = "line2" 改为 pc = "line3".

在 NAND-CIRC 中, GOTO 只能向代码后方跳转. 但由于 NAND-TM 的所有内容都包含在一个大型外层循环中, 可以使用相同思路实现向代码前方跳转的 GOTO 以及条件循环.

其他循环. 有了 GOTO 后, 也可以在 NAND-TM 中模拟所有标准循环结构, 例如 while、do .. until 或 for. 例如, 可以将代码

while foo:
    do blah
do bar

替换为

"loop":
    if NOT(foo): GOTO("next")
    do blah
    GOTO("loop")
"next":
    do bar

for j in range(100):
    do something

do blah

7.5 均匀性以及 NAND 与 NAND-TM 的比较 (讨论)

尽管 NAND-TM 在 NAND-CIRC 的基础上增加了额外操作, 但说 NAND-TM 程序或图灵机比 NAND-CIRC 程序或布尔电路“更强大“并不完全准确. NAND-CIRC 程序没有循环, 因而根本不适用于计算输入数量无界的函数. 因此, 为了使用 NAND-CIRC (或等价的布尔电路) 计算函数 $F:\{0,1{\}}^{\ast }:\to \{0,1{\}}^{\ast },$ 我们需要一个程序或电路 集合: 每种输入长度对应一个程序或电路.

NAND-CIRC 与 NAND-TM 的关键区别在于, NAND-TM 能够表达这样一个事实: 计算长度为 $100$ 的字符串之奇偶校验的算法, 与计算长度为 $5$ 的字符串之奇偶校验的算法实际上是同一个算法 (类似地, 对每个 $n,$ $n$ 比特数的加法算法也是同一个算法). 也就是说, 可以把计算一般奇偶校验的 NAND-TM 程序视为一颗“种子“, 根据需要从中生长出计算长度为 $10$、$100$ 或 $1000$ 的字符串之奇偶校验的 NAND-CIRC 程序.

这种使用单一算法计算所有输入长度之函数的概念称为计算的 均匀性. 因此, 图灵机和 NAND-TM 被视为 均匀 计算模型; 与之相对, 布尔电路和 NAND-CIRC 是 非均匀 计算模型, 必须为每种输入长度指定不同的程序.

展望后文, 我们将看到这种均匀性还会导致图灵机与电路之间的另一个关键区别. 图灵机的输入和输出可以长于该机器自身的字符串描述. 特别地, 存在能够“自我复制“的图灵机, 即它可以打印自己的代码. “自我复制“以及与之相关的“自指“概念, 对计算的许多方面都至关重要, 对生命本身亦是如此, 无论生命采取数字程序还是生物程序的形式.

目前, 你应当记住 均匀 计算模型与 非均匀 计算模型之间的以下区别:

• 非均匀计算模型: 例如 NAND-CIRC 程序 和 布尔电路. 在这些模型中, 每个单独的程序或电路可以计算一个 有限 函数 $f:\{0,1{\}}^n\to \{0,1{\}}^m.$ 我们已经看到, 每个 有限函数都能由 某个 程序或电路计算. 为了讨论 无限 函数 $F:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ 的计算, 需要允许使用程序或电路的一个 序列 $\{P_n{\}}_{n\in \mathbb{N}}$ (每种输入长度对应一个), 但这无法刻画使用 单一算法 计算函数 $F$ 的概念.

• 均匀计算模型: 例如 图灵机 和 NAND-TM 程序. 在这些模型中, 单个程序或机器可以接受 任意长度 的输入, 因而能够计算 无限 函数 $F:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }.$ 程序或机器在某个输入上执行的步骤数不存在预先确定的先验上界. 特别地, 它有可能进入 无限循环. 与非均匀情形不同, 我们尚未证明每个无限函数都能由某个 NAND-TM 程序或图灵机计算. 我们将在第 9 章重新讨论这一点.

7.6 习题

7.7 参考文献说明

Lovelace 伯爵夫人 Augusta Ada Byron (1815-1852) 的一生短暂而坎坷, 如今她最为人所知的是与 Charles Babbage 的合作 (传记见 Stein, 1987). Ada 对 Babbage 的 分析机 表现出浓厚兴趣, 我们曾在第 3 章提到这台机器. 1842 至 1843 年间, 她把 Menabrea 一篇讨论分析机的论文从意大利语译出, 并加入了大量注释 (篇幅超过论文本身). 本章开头的引文取自该文本的注释 A. Lovelace 的注释包含多个分析机 程序 示例, 因此她被称为“世界上第一位计算机程序员“. 不过, 尚不清楚这些程序究竟出自 Lovelace 还是 Babbage 本人 Holt, 2001. 无论如何, Ada 显然是极少数充分认识到计算机械化这一思想真正具有何等重要性和革命性的人之一 (或许除 Babbage 本人外仅有她一人).

Shetterly Shetterly, 2016 和 Sobel Sobel, 2017 的著作讨论了人类计算员 (其中大多数是女性) 的历史, 以及她们对天文学和太空探索领域科学发现的重要贡献.

Alan Turing 是 20 世纪的思想巨匠之一. 他不仅是第一个定义计算概念的人, 还在第二次世界大战期间为破解 Enigma 密码发明并使用了世界上最早的一批计算设备, 挽救了数百万人的生命. 不幸的是, Turing 于 1952 年因同性性行为被定罪并接受法院强制的激素治疗, 后于 1954 年自杀. 2009 年, 英国首相 Gordon Brown 正式公开向 Turing 道歉; 2013 年, Elizabeth II 女王追授 Turing 皇家赦免. Turing 的一生是一部优秀著作和一部平庸电影的主题.

Sipser 的教材 Sipser, 1997 将图灵机定义为一个 七元组, 由状态空间、输入字母表、磁带字母表、转移函数、初始状态、接受状态和拒绝状态组成. 表面上看, 这一定义与 定义 7.1 大不相同, 但它只是同一概念的另一种表示, 正如图既可以用邻接表表示, 也可以用邻接矩阵表示.

其中一个区别是, Sipser 考虑一般的状态集合 $Q,$ 它不一定对某个自然数 $k>0$ 具有 $Q=\{0,1,2,\dots ,k-1\}$ 的形式. Sipser 还将讨论限制在只输出单个比特的图灵机上, 因而指定了两个特殊的 停机状态: “$0$ 停机状态” (通常称为 拒绝状态) 和 “$1$ 停机状态” (通常称为 接受状态). 因此, 机器不会在输出磁带上写入 $0$ 或 $1,$ 而是进入这两个状态之一并停机. 这同样不会改变计算能力, 不过我们更倾向于考虑输出多个比特的更一般模型. (Sipser 把图灵机的基本任务表述为 判定语言 而非计算函数, 但两者等价, 见 备注 7.1.)

Sipser 还考虑输入属于 ${\Sigma }^{\ast }$ 的函数, 其中 $\Sigma$ 是任意字母表 (因此, 他区分记作 $\Sigma$ 的 输入字母表 与记作 $\Gamma$ 的 磁带字母表), 而我们只关注以二进制字符串为输入的函数. 这同样不是什么大问题, 因为总能用长度为 $\log \lceil |\Sigma |\rceil$ 的二进制字符串编码 $\Sigma$ 中的元素. 最后 (这是非常次要的一点), Sipser 要求机器在每一步中必须向左或向右移动, 不提供停留操作 $\mathsf{S}.$ 不过, 只需先向右移动再向左返回, 就能轻易模拟停留在原处.

文献中还使用另一种定义: 如果对每个 $x\in L$ 都有 $M(x)=1,$ 且对每个 $x\notin L$ 都有 $M(x)\in \{0,\perp \},$ 则称图灵机 $M$ 识别 语言 $L.$ 如果存在一台识别语言 $L$ 的图灵机 $M,$ 则称 $L$ 是 递归可枚举的; 所有递归可枚举语言构成的集合通常记为 $\mathbf{RE}.$ 本书不会使用这一术语体系.

图灵机最早的一批编程语言表述之一由 Wang Wang, 1957 给出. 我们对 NAND-TM 的表述旨在使其与电路之间的联系更加直接, 最终用于 Cook-Levin 定理以及 $\mathbf{P}\subseteq {\mathbf{P}}_{/poly}$ 和 $\mathbf{BPP}\subseteq {\mathbf{P}}_{/poly}$ 等结论. 网站 esolangs.org 收录了种类繁多的深奥图灵完备编程语言. 其中最著名的语言之一是 Brainf*ck.

1: 从集合 $A$ 到集合 $B$ 的 偏函数 $F$ 是只在 $A$ 的某个 子集 上有定义的函数 (见第 1.4.3 节) .也可以把这样的函数看作从 $A$ 映射到 $B\cup \{\perp \},$ 其中 $\perp$ 是一个特殊的 “失败” 符号, $F(a)=\perp$ 表示函数 $F$ 在 $a$ 上未定义.

2: 大多数编程语言使用固定大小的数组, 而图灵机的磁带是无界的. 当然, 我们没有必要存储无限多个 $\varnothing$ 符号. 可以把磁带看作一个列表: 它最初只需足够长以存储输入, 随着图灵机的磁头探索新位置, 再动态扩展其大小.

3: 可以使用序列 $\mathsf{R}$、$\mathsf{L}$、$\mathsf{R}$、$\mathsf{R}$、$\mathsf{L}$、$\mathsf{L}$、$\mathsf{R}$、$\mathsf{R}$、$\mathsf{R}$、$\mathsf{L}$、$\mathsf{L}$、$\mathsf{L}$、$\dots .$