PDA到图灵机的转换

Question

我必须将给定的PDA转换为Turing机器形式，并且正在努力寻找有关如何执行此操作的资源。如果有人可以向我解释或指出一些可以解释如何做的资源，将不胜感激。

Answer 1

正如Welbog在评论中所建议的那样，只需像堆叠一样使用磁带：

1. 当PDA推入堆栈时：

   • 仅保留当前的磁带符号
   • 将磁带头移到右边
   • 将符号写到磁带上并保持在原处

2. 当PDA从堆栈中弹出时：

   • 将当前符号替换为空白
   • 将磁带头移到左侧

注意，这种构造意味着PDA中的每个“推”转换都需要TM中有一个额外的中间状态，以处理两步先移后写的操作。您可以采用不同的方法来构造此结构，因此可能可以对pop操作采取额外的步骤。