图灵机#

定义是一个七元组：

• $Q$ 是一个有限的状态集合
• $\Sigma$ 是一个有限的输入符号集合
• $\Gamma$ 是一个有限的带符号集合，且 $\Sigma \subseteq \Gamma$
• $\delta$ 是一个状态转移函数，定义为 $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$
• $q_0 \in Q$ 是初始状态
• $B \in \Gamma$ 是空白符号，且 $B \notin \Sigma$
• $F \subseteq Q$ 是接受状态集合

图灵机有一条无穷长的纸带，上面一个格子能存一个字符，可以当做内存来用了

绘制图灵机#

使用形如$a/b \leftarrow$来表示一次状态转移，如果读头当前所在的格子为$a$则读入，并写入符号$b$，然后使读头向左移动一格

图灵机的三种运行结果#

1. 接受并停机：到达$q_{f}$/$q_{accept}$/Acc，则判断输入字符串被接受，图灵机停机
2. 拒绝并停机：到达$q_{r}$/$q_{reject}$/Rej，则判断输入字符串被拒绝，图灵机停机
3. 循环：永远运行，不到达任何停机状态，表示不接受输入字符串

技巧#

同样可用自定义符号表示结构化信息

示例：解决$a^n b^n c^n$问题#

题里会告诉读头的初始位置，此题假设读头初始位置在最左边的第一个字符上

1. 几种情况：
   • 此处为$a$，替换为$X$，并向右移动，进入步骤2
   • 此处为$X$，说明所有的$a$都已经被替换，进入步骤8
   • 此处为$b$或$c$，判断输入字符串被拒绝，图灵机停机
   • 此处为字符串边界或空白符$B$，判断输入字符串被接受，图灵机停机
2. 看到$a$或$Y$就继续向右
3. 直到：
   • 遇到一个$b$，将其替换为$Y$，并向右移动，进入步骤4
   • 遇到一个$c$，判断输入字符串被拒绝，图灵机停机
   • 遇到字符串边界或空白符$B$，判断输入字符串被拒绝，图灵机停机
4. 看到$b$或$Z$就继续向右
5. 直到：
   • 遇到一个$c$，将其替换为$Z$，并向左移动，进入步骤6
   • 遇到一个$a$，判断输入字符串被拒绝，图灵机停机
   • 遇到字符串边界或空白符$B$，判断输入字符串被拒绝，图灵机停机
6. 看到$a,b,Y,Z$就继续向左
7. 直到：
   • 遇到一个$X$，不修改，向右移动，进入步骤1
   • 遇到字符串边界或空白符$B$，说明所有的$a$都已经被替换，进入步骤8
8. 一直向右移动，直到：
   • 若遇不到任何$c$或$b$而是到达字符串边界或空白符$B$，则判断输入字符串被接受，图灵机停机
   • 若遇到$b$或$c$，则判断输入字符串被拒绝，图灵机停机