图灵机

图灵机

• Tape：无限长的纸带，被划分为多个单元，各存有某一符号
• Head：读写头
  • 对准某一单元
  • 可以读取或改写其中的字符
  • 每拍可以向左或向右移动一个单元
• State：状态，每拍可按规则转向另一种状态
• Alphabet：语言，有限种符号 Transition Function: $(q,c;d,L/R,p)$ 当前状态为$q$，字符为$c$，将当前字符修改为$d$，读写头向左或向右移动，状态修改为$p$

从启动到停机经历的节拍数目或 Head 的累计移动步数可用于衡量算法的优劣。

实例

二进制加 1 注意最后复位也算一步。

Example

初始状态下读写头所对单元格为 0，其余为 #，连续执行 increase() 算法 2014 次，读写头移动次数最接近于？

读写头移动次数取决于最低位有多少个连续的 1，每有一次进位，移动次数加 2，同时每次执行 increase() 算法都固定有右行后复位的 2 个操作。 总共有 $2014\left(\frac{1}{2}+\frac{1}{4}+\dots \right)\approx 2014$ 次进位，共执行了 2014 次 increase() 算法，因此读写头移动次数约为 $2\cdot 2014+2\cdot 2014\approx 8000$ 次

形式定义

图灵机是一个七元组：

$$M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,F)$$

• $Q$：状态的有穷集合
• $\Sigma$：输入符号的有穷集合
• $\Gamma$：带符号的有穷集合，$\Sigma \subseteq \Gamma$
• $\delta$：转移函数，$\delta (q,X)$ 在有定义时是三元组 $(p,Y,D)$，其中
  • $p$ 是下一状态，$Y\in \Gamma$ 是在当前扫描单元中写下的符号，$D\in \{L,R\}$ 是方向
• $q_0$：初始状态
• $B$：空格符号，$B\in \Gamma -\Sigma$，开始时，空格出现在除包含输入符号的有穷多个初始单元外的所有单元中
• $F$：接受状态集合

当前格局用字符串 $X_1{X}_2\dots X_{i-1}q{X}_i\dots X_n$ 表示，称为 ID

• $q\in Q$ 为当前状态
• 当前带头正在扫描 $X_i$
• $X_1{X}_2\dots X_n$ 为当前当中最左端的非空白符号与最右端的非空白符号之间的带符号串。当带头超出非空白符号的范围时，$X_1\dots X_n$ 的某个前缀或后缀为空白符号串

若 $\delta (q,X_i)=(p,Y,L)$，则

$$X_1{X}_2\dots X_{i-1}q{X}_i\dots X_n⊢X_1\dots X_{i-2}p{X}_{i-1}Y{X}_{i+1}\dots X_n$$

• $i=1$ 时，$q{X}_1{X}_2\dots X_n⊢pBY{X}_2\dots X_n$
• $i=n$ 且 $Y=B$ 时，$X_1\dots X_{n-1}q{X}_n⊢X_1\dots X_{n-2}p{X}_{n-1}$ $D=R$ 时同理

Example

设计图灵机接受 $\{0^n{1}^n|n\ge 1\}$ 每次匹配将最左侧未匹配的 0 标记为 X，然后找到第一个未匹配的 1 标记为 Y，反向再找到最靠右的 X，重复。 $q_0$ 表示 0 和 1 数量相同的状态，若下一个元素已经是 Y，即已经匹配完，则移动到串的末尾并接受

Example

带有相同个数的 0 和 1 的串 分两种情况，最左的 0 找最左的 1 或最左的 1 找最左的 0 每次碰到一个未匹配的字符，标为 X，向右查找第一个和它匹配的字符，标为 Y 后反向回到第一个 X，重复。

Example

$\{a^{2^n}|n\ge 0\}$ 每次消除偶数位置的 $a$，然后返回到开头，若只剩一个 $a$，则接受，否则重复。

Example

先重复替换掉最左端和最右端的字符，此时带头会停在中间位置。然后将左半段字符串替换回来，从左向右逐个匹配左半段和右半段串是否一致。因此接受语言 $\{ww|w\in \{0,1{\}}^{+}\}$

图灵机的程序设计技术

在状态中存储

状态视为元组，状态中可以包含一个有有限个取值的存储单元 $Q=S\times T=\{[q,a]|q\in S\wedge a\in T\}$

多道

带符号视为元祖

子程序

子程序是一个状态集合，包含初始状态和一个返回状态，当存在到初始状态的转移时发生子程序的调用，返回状态则把控制交回给调用子程序的状态。若有多个状态调用一个子程序，可以复制子程序。

Example

设计一个程序，将 $0^{m}10^{n}1$ 转换为 $0^{mn}$ 首先设计一个子程序，将 $0^{m-k}1q_1{0}^{n}10^{(k-1)n}$ 变成 $0^{m-k}1q_5{0}^{n}10^{kn}$ 完整的乘法如下：

基本图灵机的扩展

多带图灵机

输入在第一条带上，其余带所有单元格都为空格。 每步移动中，在每条带上写新的带符号，每个带头独立移动，可以左移、右移或静止。

接受能力与单带图灵机等价。 证明：可以用多道图灵机模拟多带图灵机，用 $2k$ 个道的图灵机模拟 $k$ 个带的图灵机，对于每条带，一个道存带头位置，一个道存带的内容。

非确定型图灵机

转移变为三元组的集合。

非确定型图灵机接受能力和图灵机等价。 证明：可以构造多带图灵机模拟非确定型图灵机。 双带图灵机，一条带为队列，存将要搜索的 ID，第二条带是草稿，根据正在处理的 ID 计算出下一步移动后的所有可能 ID 并添加到队列末尾。

受限制的图灵机

半无穷带

带头初始位置左部没有单元格 可以用双道的半无穷带模拟双向无穷带的图灵机，因此二者接受能力等价

多堆栈机

具有多个下推栈的 DPDA，总是假设输入是带有结束标记的。 多带图灵机可以模拟多堆栈机。

一个 2 堆栈机也可以模拟图灵机：首先读取输入至结束标记，把所有输入压入第一个堆栈；然后依次弹出第一个堆栈中除栈底每个字符，压入第二个堆栈；接下来开始模拟图灵机的移动，第一个下推栈模拟当前带头位置左边的单元格，而第二个下推栈模拟当前带头位置右边（包含当前）的单元格。

计数器机

结构与多堆栈机相同，但是用计数器代替每个堆栈。 只能区分零计数器与非零计数器。 不允许计数器为负。 具有两个或以上计数器的计数器机的接受能力等同于图灵机。

图灵机与计算机

可以用多带图灵机模拟计算机 第一条带表示存储 第二条带表示指令计数器 第三条带保存当前和需访问的存储地址 第四条带保存被模拟的计算机输入，因为计算机可以从文件读输入 第五条带是一条草稿带，模拟有些计算机指令可能有效地使用一条或多条草稿带来计算，诸如乘法的算术运算