图灵机的状态图以字典顺序计算下一个字符串

Question

对于图灵机来说，状态图会是什么样的，它以字母顺序Σ= {1,2,3}计算字典顺序中的下一个字符串？字符串大小为4，即--- 1，--- 2，--- 3， - 11， - 12等...

已经尝试过从Michael Sipser的计算理论导论中找出它而没有运气。还尝试在线查找，再次没有运气。

提前致谢！

Answer 1

如果我已正确理解，您希望TM将长度为{1,2,3}的字符串作为输入，最多为4，并用字母顺序覆盖下一个相同字母表的字符串覆盖此数字。以下是此问题的策略。

1. 向右移动三次，这样我们就可以看到磁带上的第四个符号。
2. 如果这是空白，我们的输入结果是错误的，我们就死了。否则，如果符号为1，则写入2并停止接受;如果为1，则写入2并停止接受; if 3，写1并向左移动状态“carry2”
3. 如果这是空白，1或2，分别写入1,2或3，并停止接受。 if 3，写1并向左移动状态“carry3”
4. 如果这是空白，1或2，分别写入1,2或3，并停止接受。 if 3，写1并向左移动状态“carry4”
5. 如果这是空白，1或2，分别写入1,2或3，并停止接受。如果为3，则输入数字为3333，并且在{1,2,3}上没有按字典顺序排列的较大的4位数字符串......所以要么崩溃，要么将包装和写入-1写入磁带。

请注意，这并不能验证磁带内容是否正常...因为我们使用空格来编码“缺失”的高位数字，我们可以合理地假设磁带上的位置4之后没有任何内容（定义我们的TM小心翼翼地避免暗示我们在那之后做了什么）。此外，我们没有对前端进行消毒，因此不正确地混合符号和空白可能是一个问题......所以我们可以先运行一些步骤来验证输入，或者只是在我们得到输入时要求输入结构良好。