请考虑一种“堆栈翻转机”变体，该变体可以使用无限个磁带和一个堆栈进行操作。在遍历磁带的每一步中，机器都会从当前磁带位置和堆栈顶部读取输入，然后转换状态，写入磁带，然后沿着磁带移动（就像经典的TM一样），并且还会弹出从和/或推入堆栈（例如经典PDA）。换句话说：经典TM具有转换功能：𝛿（𝑞𝑖，𝑎）→（𝑞𝑗，𝑏，𝐿𝑅）其中q是状态，a和b是磁带的输入/输出，经典PDA具有转换功能：𝛿（ 𝑞𝑖，𝑐）→（𝑞𝑗，𝑑）其中q是状态，c是堆栈的初始顶部，d是新推入堆栈的顶部stack-TM具有转换函数𝛿（𝑞𝑖，𝑎，𝑐）→（𝑞𝑗，𝑏 ，𝐿，𝑅，𝑑）合并TM和PDA证明Stack-Turing Machine等效于Classic TM。
！（https://imgur.com/a/daJgTTb）不确定如何处理。
不涉及任何代码；计算证明理论。
没有，这是一个计算证明理论。
Stack-TM可以通过对堆栈不做任何有趣的事情来模拟常规TM。通过将第二个磁带视为堆栈，双带TM可以模拟Stack-TM（仅写到末尾，并通过清除符号从末尾读取）。最后，常规TM可以模拟两带TM，因为我们知道多带TM等同于单带TM（假设我们知道此结果）。由于模拟关系的传递性，所有系统都是等效的，因为它们可以互相模拟。