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

Question

问题：给定一个开始状态 q0 和一个完全空白的磁带，除了一个带有 # 符号的正方形，找到 # 并在它上面停下来。

非确定性：

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

确定性： ?

如何以确定的形式复制这台机器？我做了一些研究，似乎可以通过解决“树”的两种可能性/分支来解决这个问题，但我似乎无法在这里连接这些点......

Answer 1

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

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

通过这种方式，您可以以确定性的方式处理任何固定数量的非确定性分支。当然，跑来跑去比实际模拟需要更多的时间。