2

图灵机在字母 Σ = {1, 2, 3} 上按字典顺序计算下一个字符串的状态图会是什么样子?字符串大小为4,即---1、---2、---3、--11、--12等...

已经尝试从 Michael Sipser 的“计算理论导论”中弄清楚,但没有运气。还尝试在网上查找它,再次没有运气。

提前致谢!

4

1 回答 1

1

如果我理解正确,您希望 TM 将超过 {1, 2, 3} 的字符串作为输入,长度不超过四,并用字符串覆盖此数字,该字符串按字典顺序排在下一个字母表上。这是解决此问题的策略。

  1. 向右移动 3 次,所以我们正在查看磁带上的第四个符号。
  2. 如果这是空白,我们的输入是错误的,我们会死。否则,如果符号为 1,则写入 2 并停止接受;如果为 1,则写入 2 并停止接受;如果为 3,则写入 1 并在状态“carry2”中向左移动
  3. 如果这是空白、1 或 2,则分别写 1、2 或 3,然后停止接受。如果为 3,则写入 1 并在状态“carry3”中向左移动
  4. 如果这是空白、1 或 2,则分别写 1、2 或 3,然后停止接受。如果为 3,则写入 1 并在状态“carry4”中向左移动
  5. 如果这是空白、1 或 2,则分别写 1、2 或 3,然后停止接受。如果为 3,则输入是数字 3333,并且在 {1, 2, 3} 上没有字典上更大的 4 位字符串……所以要么崩溃,要么换行并将 ---1 写入磁带。

请注意,这并不能验证磁带内容是否正常......因为我们使用空格来编码“丢失”的高位数字,我们可以合理地假设磁带上的第 4 位之后没有任何内容(仔细定义我们的 TM 所做的事情以避免暗示我们在那之后做了任何事情)。此外,我们没有对前面进行消毒,因此不正确地混合符号和空格可能是一个问题……所以我们可以先运行一些步骤来验证输入,或者在我们得到它时只要求输入格式正确。

于 2019-04-01T18:30:52.170 回答