我有这个问题：考虑一个图灵机Cw，它擦除它的输入，在磁带上写w，并在扫描w的最左边的字符时停止 . 设计图灵机C011
我需要解释实际问题是什么以及Cw做了什么 . 我有点理解它在每个输入上都写出空符号，但其余部分对我来说都不清楚 . 希望有人能帮助我理解这个问题以及我需要做什么 .
在你的情况下，w = 011 .
实际上，TM应首先覆盖整个输入 . 我想我们可以假设输入没有差距 . 因此，一旦TM读取输入磁带上的空白区域，它就应该开始写入011 .
写入第二个1时，进入不存在任何转换的状态 . 这样可以确保机器在该位置停止 . 没有任何关于这个国家是否应该接受的明确说法，但将它作为独特的接受国是有意义的 .
1 回答
在你的情况下，w = 011 .
实际上，TM应首先覆盖整个输入 . 我想我们可以假设输入没有差距 . 因此，一旦TM读取输入磁带上的空白区域，它就应该开始写入011 .
写入第二个1时，进入不存在任何转换的状态 . 这样可以确保机器在该位置停止 . 没有任何关于这个国家是否应该接受的明确说法，但将它作为独特的接受国是有意义的 .