Search code examples
infinite-looptheorycomputation-theoryturing-machinesinput-language

How can a string that does not belongs to the input language can set a turing machine in a infinite loop?


How is it possible to set a turing machine in infinite loop by putting a string that doesn't belong to input language even if it has a reject state?


Solution

  • Consider the TM that does the following:

    1. Read a tape cell. If 0, halt accept. If 1, write 1, move right, and enter state 2.
    2. Read a tape cell. If 0, halt reject If 1, write 1, move left, and enter state 1.

    This machine accepts strings 0* + 10*. It does not accept anything in 11* but it will loop forever on such a string.