用确定性图灵机模拟非确定性图灵机[JFLAP]

Question

问题：给定一个起始状态 q0 和一个完全空白的磁带，除了一个带有 # 符号的方块，找到 # 并在其上停止。

非确定性：

这台机器选择在起始状态的左侧或右侧搜索，并继续朝那个方向前进，直到下一个符号是# 符号，它停留在那里。

确定性地：?

如何以确定性形式复制这台机器？我做了一些研究，似乎可以通过解决 "tree" 的 possibilities/branches 来解决这个问题，但我似乎无法将这里的点联系起来...

Answer 1

您不仅要 运行 处理非 # 单元格，还要将它们标记为已访问。此外，您可以通过在两个分支之间交替来同时执行这两个分支。

1. 用“+”标记当前单元格（除非它已经是#）
2. 运行右边的同时你看到了+。当您看到第一个空白时，将其标记为 +.
3. 运行 左手边看+。当您看到第一个空白时，将其标记为 +。转到 2.

通过这种方式，您可以确定性地处理任意固定数量的非确定性分支。当然，运行宁周围比实际模拟花费的时间要多得多。