其它计算模型

• 下推自动机(Pushdown Automaton)
• random-access machine
• 算盘自动机(abacus machine, or register machine)
• λ-calculus
• 组合逻辑(combinatory logic)
• cellular automaton
• μ-recursive function
• abstract rewriting system

下推自动机(Pushdown Automaton, PDA)是一个带有下推存储器的有限自动机,下推存储器是一个栈。

下推自动机包括一个6元组$M=(\mathrm{\Sigma },\mathrm{\Gamma },Q,\mathrm{\Delta },s,F)$$M = (\Sigma,\Gamma,Q,\Delta,s,F)$:

• $\mathrm{\Sigma }$$\Sigma$是包含空字符$\beta$$\beta$的条带字符集
• $\mathrm{\Gamma }$$\Gamma$是包含空字符$\gamma$$\gamma$的栈字符集
• $Q$$Q$是有限状态集
• $\mathrm{\Delta }\subseteq (Q\times (\mathrm{\Sigma }\cup ϵ)\times (\mathrm{\Gamma }\cup ϵ)\times Q\times (\mathrm{\Gamma }\cup ϵ))$$\Delta\subseteq(Q\times(\Sigma\cup{\epsilon})\times(\Gamma\cup{\epsilon})×Q×(\Gamma\cup{\epsilon}))$是状态迁移规则
• $s$$s$是初始状态
• $F$$F$是最终状态集

如果$M$$M$的状态迁移规则是:$(p,x,y;q,z)\in \mathrm{\Delta }$$(p,x,y;q,z)\in\Delta$, 当前状态是$p$$p$,条带字符是$x$$x$,栈字符是$y$$y$, 那么$M$$M$从栈顶取出$y$$y$, 将$z$$z$压入栈, 进入状态$q$$q$.

如果任何时刻的迁移规则是确定的, 称该下推自动机是确定性的(deterministic), 否则称为非确定性的(nondeterministic).

如果状态迁移规则是$(p,x,ϵ;q,ϵ)$$(p,x,\epsilon;q,\epsilon)$, 栈的功能被忽略, PDA退化成FSM. 所以, PDA也能接受正则语言。

由于有栈的支持,下推自动机能够接受FSM不能接受的语言。

下推自动机能够接受的语言称为上下文自由语言( Context-Free Languages, CFL).

算盘机(Abacus Machine)是以算盘为基础的计算模型。

模拟算盘机的图灵机设计如下:

| 当前状态 | 当前符号 | 新状态 | 新符号 | 移动方向 | | 1 | 0 | 2 | 1 | 1 | | 1 | 1 | 2 | 1 | 1 | | 2 | 0 | 3 | 0 | 1 | | 2 | 1 | 2 | 1 | 1 | | 3 | 0 | 4 | 1 | 1 | | 3 | 1 | 4 | 1 | 1 | | 4 | 0 | 5 | 0 | 1 | | 4 | 1 | 4 | 1 | 1 | | 5 | 0 | 6 | 1 | 1 | | 5 | 1 | 6 | 1 | 1 | | 6 | 0 | 8 | 1 | 1 | | 6 | 1 | 6 | 1 | 1 | | 7 | 1 | 8 | 1 | 1 | | 8 | 0 | 9 | 0 | -1 | | 8 | 1 | 11 | 0 | 1 | | 9 | 0 | 10 | 0 | -1 | | 9 | 1 | 9 | 1 | -1 | | 10 | 0 | 13 | 0 | 1 | | 10 | 1 | 9 | 1 | -1 | | 11 | 0 | 8 | 1 | 1 | | 11 | 1 | 11 | 1 | 1 | | 12 | 0 | 11 | 0 | 1 | | 13 | 0 | 14 | 0 | 1 |

运行结果：

• 00110111101110101100-s-1-h-3
• 00110111101110101100-s-2-h-4
• 00110111101110101100-s-2-h-5
• 00110111101110101100-s-3-h-6
• 00110111101110101100-s-4-h-7
• 00110111101110101100-s-4-h-8
• 00110111101110101100-s-4-h-9
• 00110111101110101100-s-4-h-10
• 00110111101110101100-s-5-h-11
• 00110111101110101100-s-6-h-12
• 00110111101110101100-s-6-h-13
• 00110111101110101100-s-6-h-14
• 00110111101111101100-s-8-h-15
• 0110111101111001100-s-11-h-16
• 00110111101111011100-s-8-h-17
• 0110111101111010100-s-11-h-18
• 0110111101111010100-s-11-h-19
• 00110111101111010110-s-8-h-20
• 00110111101111010110-s-9-h-19
• 00110111101111010110-s-9-h-18
• 00110111101111010110-s-9-h-17
• 0110111101111010110-s-10-h-16
• 00110111101111010110-s-9-h-15
• 0110111101111010110-s-10-h-14
• 00110111101111010110-s-9-h-13
• 00110111101111010110-s-9-h-12
• 00110111101111010110-s-9-h-11
• 00110111101111010110-s-9-h-10
• 00110111101111010110-s-10-h-9
• 00110111101111010110-s-9-h-8
• 00110111101111010110-s-9-h-7
• 00110111101111010110-s-9-h-6
• 00110111101111010110-s-9-h-5
• 00110111101111010110-s-10-h-4
• 00110111101111010110-s-9-h-3
• 00110111101111010110-s-9-h-2
• 00110111101111010110-s-10-h-1
• 00110111101111010110-s-13-h-2
• 00110111101111010110-s-14-h-3

最终停止在状态：

• 00110111101111010110-s-14-h-3

对比初始状态：

• 00110111101110101100-s-1-h-3

往第3个盒子里增加一个球已模拟成功。

感兴趣的同学, 可以再验证一下以下初始状态的运行结果:

• 001101110110101100-s-1-h-3

算盘机能够实现图灵机能实现的加法和乘法等运算。

图灵机能够实现算盘机能实现的盒子加法和减法。

算盘机与图灵机的计算能力相当。