是那张留在第一符号

Question

图灵机我有一个图灵机与下表

我输入字符串AAAA给出过渡。因此，如果我在状态A中查看第一个符号“a”，则说它用X代替它，进入状态B并向左移动。这是我困惑的地方。如果我正在查看第一个输入符号，我该如何左移？我只是去空白符号？

谢谢！

Answer 1

它依赖于你正在考虑的图灵机的变种。如果您考虑使用“标准”图灵机，磁带对于双方都是无限的，并且通过移动输入上留下的标题，您会得到一个空白符号。

但是，如果您的磁带仅限于右侧，则无法在到达第一个符号后向左移动。为了简单起见，您可以通过在磁带的开头处向左移动来确定，您将保留在第一个输入符号上。