考虑一个"堆栈图灵机"变体，它使用一个无限磁带和一个堆栈运行。在磁带的每一步，机器从当前磁带位置和堆栈顶部读取输入，然后转换状态，写入磁带，沿着磁带移动(如经典TM)，也可以从堆栈弹出和/或推送到堆栈(如经典PDA)。换句话说：经典TM具有转换功能：δ(qi，a)→(qj，b，L∪R)，其中q是状态，a和b是磁带的输入/输出 经典PDA具有转换功能：δ(qi，c)→(qj，d)，其中q是状态，c是堆栈的初始顶部，d是新推送的堆栈顶部 堆栈TM具有转移函数δ(qi， a，c)→(qj，b，L∪R，d)合并TM和PDA证明堆栈图灵机等价于经典TM。
！(https://i.stack.imgur.com/BaCrs.jpg) 不知道如何处理这个问题。
不涉及代码; 计算理论证明。
没有，这是一个计算证明的理论。
Stack-TM 可以通过简单地对堆栈不做任何有趣的事情来模拟常规 TM。双磁带 TM 可以通过将第二个磁带视为堆栈来模拟堆栈 TM(仅写入末尾并通过清除符号从末尾读取)。最后，常规 TM 可以模拟双磁带 TM，因为我们知道多磁带 TM 等同于单磁带 TM(假设我们知道此结果)。由于仿真关系的传递性，所有系统都是等效的，因为它们都可以相互仿真。