图灵机简介

他的抽象“机器”预示了我们现在所理解的低级计算机指令集。更重要的是，正是图灵引入了将程序作为输入的概念，并提出了对程序行为进行模拟（即“执行”程序）的思想，这一思想极大地影响了数字计算机的发展。但在我们研究图灵机之前，先来探讨一下具有两个栈的下推自动机（PDA）能做些什么。

具有两个栈的PDA与图灵机

我们知道语言 $L = a^nb^nc^n$ 不是上下文无关的，但一个具有两个栈的下推自动机可以识别它。我们使用一个栈来匹配 $a$ 和 $b$，另一个栈来匹配 $b$ 和 $c$。如下所示为识别语言 $L$ 的双栈PDA。

栈操作有两个入口——每个栈各一个。每条转移的模式为：<符号>, <弹出栈1>$\rightarrow$<压入栈1>, <弹出栈2>$\rightarrow$<压入栈2>。下表追踪了字符串 $aabbcc$ 在双栈PDA中的处理过程：

那么对于语言 $M = a^nb^nc^nd^n$ 呢？是否需要第三个栈？不需要。我们只需回到第一个栈，用它来匹配 $c$ 和 $d$。

以下是输入 $aabbccdd$ 的运行轨迹：

具有两个栈的PDA在计算能力上等价于图灵机（$\text{TM}$）。

说明：双栈PDA可以通过将图灵机读写头左侧的所有内容保存在一个栈中，其余内容保存在另一个栈中，从而模拟图灵机的行为。随着图灵机的运行，元素根据需要在两个栈之间移动或被移除。

波斯特机（Post Machine）

我们也可以通过一种称为波斯特机（又称“队列机”）的自动机获得同等的计算能力。该模型以逻辑学家埃米尔·波斯特（Emil Post）命名，其研究早于图灵和丘奇的工作。这种自动机使用队列而非两个栈，仅需一个队列即可达到图灵机的计算能力。通过使用字符串结束标记，我们可以不断循环处理输入：从队列前端取出符号并将其重新加入队列尾部。此外，不再单独设置“输入通道”——我们假设在处理开始前，队列中已预先填入以$符号分隔的输入字符串。下面的队列机可接受语言$L = a^nb^nc^n$。与通常做法一致，此处省略了对无效输入（如符号顺序错误）的处理，遇到此类情况时机器会崩溃，从而隐式拒绝该输入字符串。

边上的标注格式为 <从前端出队/向后端入队>。下表展示了该机器的运行过程：

该过程首先将遇到的第一个 $a$ 替换为 $X$，然后寻找一个 $b$ 进行替换，再找一个 $c$ 替换。当到达结束标记时，重复此过程。如果找不到 $a$，则检查队列中是否只剩下 $X$。若非如此，机器将崩溃并拒绝该输入。最终状态 $q_4$ 是一个停机状态（无输出边）。整个输入都位于队列中，因此当进入停机状态时，处理结束。