图灵机在字母 Σ = {1, 2, 3} 上按字典顺序计算下一个字符串的状态图会是什么样子?字符串大小为4,即---1、---2、---3、--11、--12等...
已经尝试从 Michael Sipser 的“计算理论导论”中弄清楚,但没有运气。还尝试在网上查找它,再次没有运气。
提前致谢!
图灵机在字母 Σ = {1, 2, 3} 上按字典顺序计算下一个字符串的状态图会是什么样子?字符串大小为4,即---1、---2、---3、--11、--12等...
已经尝试从 Michael Sipser 的“计算理论导论”中弄清楚,但没有运气。还尝试在网上查找它,再次没有运气。
提前致谢!
如果我理解正确,您希望 TM 将超过 {1, 2, 3} 的字符串作为输入,长度不超过四,并用字符串覆盖此数字,该字符串按字典顺序排在下一个字母表上。这是解决此问题的策略。
请注意,这并不能验证磁带内容是否正常......因为我们使用空格来编码“丢失”的高位数字,我们可以合理地假设磁带上的第 4 位之后没有任何内容(仔细定义我们的 TM 所做的事情以避免暗示我们在那之后做了任何事情)。此外,我们没有对前面进行消毒,因此不正确地混合符号和空格可能是一个问题……所以我们可以先运行一些步骤来验证输入,或者在我们得到它时只要求输入格式正确。