computer-science - 在第一个符号左转的图灵机

Question

我有一台带有下表给出的转换的图灵机

我正在输入字符串 aaaa。因此，如果我查看状态 A 中的第一个符号“a”，它表示将其替换为 X，进入状态 B，然后向左移动。这就是我感到困惑的地方。如果我正在查看第一个输入符号，如何向左移动？我只是去一个空白符号吗？

谢谢！

Answer 1

这取决于您正在考虑的图灵机的变体。如果您考虑“标准”图灵机，则磁带的两侧都是无限的，并且通过将标题向左移动输入，您会得到一个空白符号。

但是，如果您的磁带仅在右侧是无限的，则您的算法在到达第一个符号后不得向左移动。为简单起见，您可以通过在磁带开头向左移动来判断您停留在第一个输入符号上。