Turing 机

Turing 机是英国数学家 Alan Turing 于 1936 年提出的一种强大的计算模型, 等价于任何有限步逻辑的数学过程. 其基本思想是用机器来模拟人类用纸笔进行数学运算的过程, 它把数学运算看作下面两个步骤的组合:

•	在纸上书写或擦出某个符号;
•	把笔从纸的某处移到另一处.

这两步简单的动作就足以模拟任何数学计算. 有限状态自动机, 下推自动机都是 Turing 机的特例.

Turing 机使用无限长纸带作为它的内存, 还有一个读写头可以在纸带上读写和移动. 一开始纸带上只有输入字符串, 其他地方是空白符号. 如果需要存储某些信息, 它可以把信息写在纸带上. 要读取它写的信息, 机器可以移动读写头到对应格子处. 这台机器会一直运行直到它决定产生一个输出, 实际上当机器运行到接受状态或者拒绝状态时就会输出接受或者拒绝. 如果它始终不进入接受状态或者拒绝状态, 那么它会一直运行下去.

Turing 机是目前最主流的计算模型, 然而现实中的计算机比 Turing 机要弱一些, 因为我们并没有无限内存. Turing 机也有理论上无法解决的问题, 比如停机问题.

1形式定义

定义 1.1 (Turing 机). 一个 Turing 机是七元组 $(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{\text{接受}},q_{\text{拒绝}})$, 这里

1.	$Q$ 是非空有限的状态集;
2.	$\Sigma$ 是非空有限集, 不包含空白符号 $\bigsqcup$, 表示可能的输入字母;
3.	$\Gamma$ 是非空有限集, 且有 $\bigsqcup \in \Gamma$ 和 $\Sigma \subset \Gamma$, 所有可能可能出现在纸带上的字母;
4.	$\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R,N\}$ 是转移函数, $L,R,N$ 分别表示读写头向左或向右移动一次, 或者不动;
5.	$q_0\in Q$ 是初始状态;
6.	$q_{\text{接受}}\in Q$ 是接受状态;
7.	$q_{\text{拒绝}}\in Q$ 是拒绝状态, 这里 $q_{\text{拒绝}}\ne q_{\text{接受}}$.

2计算

Turing 机的计算过程如下: 对 Turing 机 $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{\text{接受}},q_{\text{拒绝}})$ 输入字符串 $w=w_0{w}_1\cdots w_{n-1}\in {\Sigma }^{\ast }$

1.	把 $w_0,\dots ,w_{n-1}$ 以次置于纸带的最左边 $n$ 个格子中, 剩下的格子都填空白符号 $\bigsqcup$, 注意 $\Sigma$ 不包含空白符号, 因此纸带上第一个空白符号表示了输入的结束.
2.	将读写头置于最左边格子也就是 $w_0$ 上面
3.	从初始状态 $q_0$ 开始, 假设某个时刻 $M$ 的状态是 $q\in Q$, 读写头所在的格子的字符为 $w\in \Gamma$, 设 $\delta (q,w)=(q^{\prime },w^{\prime },D)$, 然后把 $M$ 的状态设置为 $q^{\prime }$, 把当前读写头所在的格子的字母写成 $w^{\prime }$, 根据 $D$ 所指定的动作移动读写头, 如果此时读写头已经在最左边, 那么 $L$ 方向的移动就是保持在原处, 也就是读写头始终不超出左边界.
4.	开始下一轮计算, 如此重复下去. $M$ 会一直计算下去, 直到进入状态 $q_{\text{接受}}$ 或者 $q_{\text{拒绝}}$, 输出接受或者拒绝的结果, 然后停止计算; 或者一直不进入这两个状态, $M$ 会一直运行下去.

严格描述

现在我们把上面提到的纸带, 读写头等给出严格定义, 并把计算过程严格写出来.

•	$M$ 的纸带内容是一个函数 $F:\mathbb{N}\to \Gamma$, 而 $F(i)$ 表示第 $i$ 处的字母.
•	$M$ 的格局是三元组 $(F,q,e)$, 其中 $F:\mathbb{N}\to \Gamma$ 是纸带内容, $q\in Q$ 是状态, $e\in \mathbb{N}$ 代表读写头位置.
•	设 $C_1=(F_1,q_1,e_1),C_2=(F_2,q_2,e_2)$ 是 $M$ 的两个格局, 设 $\delta (q_1,F_1(e_1))=(q,w,D)$. 如果 $q_2=q$, 以及:$$e_2=\{\begin{array}{ll}{e}_1-1& \text{如果 }D=L\text{ 并且 }{e}_1\ge 1\\ e_1& \text{如果 }D=L\text{ 并且 }{e}_1=0\\ e_1& \text{如果 }D=N\\ e_1+1& \text{如果 }D=R\end{array}$$还有:$$F_2(i)=\{\begin{array}{ll}{F}_1(i)& i\ne e_1\\ w& i=e_1\end{array}$$那么我们说 $C_1$ 产生 $C_2$.
•	对于格局 $C=(F,q,e)$, 如果 $q=q_{\text{接受}}$, 那么把 $C$ 称为接受格局; 如果 $q=q_{\text{拒绝}}$, 那么把 $C$ 称为拒绝格局; 接受格局和拒绝格局统称为停机格局.

定义 2.1 (接受或拒绝字符串). 对于 Turing 机 $M$, 和字符串 $w=w_0\cdots w_{n-1}\in {\Sigma }^{\ast }$, 若存在有限格局序列 $C_1,\dots ,C_k$ 使得:

•	$C_1$ 是起始格局, 也就是 $C_1=(F,q_0,0)$, 这里$$F(i)=\{\begin{array}{ll}{w}_i& i=0,\dots ,n-1\\ \bigsqcup & i\ge n\end{array}$$
•	对于 $i=1,\dots ,k-1$, 格局 $C_i$ 生成格局 $C_{i+1}$.
•	$C_k$ 是停机格局.

如果 $C_k$ 是接受格局 (或拒绝格局) 那么称 $M$ 接受 (或拒绝) 字符串 $w$.

所有能被 $M$ 所接受的字符串称为被 $M$ 识别的语言.

如果一个形式语言能被某个 Turing 机识别, 那么称其为 Turing-可识别语言.

我们能看到, 当一个字符串输入到某个 Turing 机, 开始计算后有三种可能: 接受, 拒绝, 或者不停机也就是循环. Turing 机 $M$ 拒绝一个输入字符串, 可能是因为进入了拒绝状态, 也可能陷入了循环. 但是有时候我们难以区分 $M$ 是陷入了循环还是只是运行时间过长. 因此我们会希望 $M$ 能始终给出结果而不会陷入循环.

定义 2.2 (可判定语言). 一个形式语言称为 Turing-可判定的, 或简称可判定的指的是存在一个 Turing 机 $M$ 使得这个语言中的每个字符串都被 $M$ 接受或拒绝.

术语翻译

格局 • 英文 configuration

识别 • 英文 recognizable

可判定的 • 英文 decidable