我有一台图灵机，下表给出了转换
我正在输入字符串aaaa . 因此，如果我查看状态A中的第一个符号“a”，它表示用X替换它，进入状态B，然后向左移动 . 这是我困惑的地方 . 如果我正在查看第一个输入符号，怎么能向左移动？我只是去一个空白的符号？
谢谢！
它取决于您正在考虑的图灵机的变体 . 如果您考虑使用“标准”图灵机，两侧的磁带都是无限的，并且通过在输入端移动 Headers ，您将得到一个空白符号 .
但是，如果您的磁带只是右侧的磁带，则您的算法在到达第一个符号后不得向左移动 . 为简单起见，您可以通过在磁带的开头向左移动来确定第一个输入符号 .
1 回答
它取决于您正在考虑的图灵机的变体 . 如果您考虑使用“标准”图灵机，两侧的磁带都是无限的，并且通过在输入端移动 Headers ，您将得到一个空白符号 .
但是，如果您的磁带只是右侧的磁带，则您的算法在到达第一个符号后不得向左移动 . 为简单起见，您可以通过在磁带的开头向左移动来确定第一个输入符号 .