infinite-loop - 一个不属于输入语言的字符串怎么能让图灵机陷入死循环呢？

Question

即使它具有拒绝状态，如何通过放置一个不属于输入语言的字符串来将图灵机设置为无限循环？

Answer 1

考虑执行以下操作的 TM：

1. 阅读磁带单元。如果为 0，则停止接受。如果为 1，则写 1，向右移动，进入状态 2。
2. 阅读磁带单元。如果为 0，则停止拒绝 如果为 1，则写入 1，向左移动，并进入状态 1。

这台机器接受字符串 0* + 10*。它不接受 11* 中的任何内容，但它会在这样的字符串上永远循环。