Search code examples
formal-languages

What this turing machine does as undecidable?

I am new for formal languages. Here is the question from the textbook. Could you give me an example of a Turing machine with two halting states, y and n, that does not decide a language ?

This is the solution according to manual. turing machine

I did not understand what machine does. Especially, when reading the input where is the tape head going right or left? Or, is this a nondeterministic machine? Could you describe what this machine does and how is this the answer of the problem?

Solution

  • This is a deterministic finite automaton. It is not undeterministic: every new symbol only has 1 possible state to go to.

    Note, that Turing machine tapes are only an "intuition pump" to help one understand how a Turing machine operates and are not its formal defintion.

    Having said that, suppose we have a transition function encoded somewhere on the tape, that is known to the machine. Whether the transition function is left or right of the input, is irrelevant, because it will jump there regardless. When the Turing machine reads a symbol (e.g. a), it

    1. goes to the location of the transition function on the memory tape (going one way, e.g. "-->")

    2. finds the new symbol, and computes the result. (reading out symbol in whichever way the transition function is written in)

    3. (case 1) If the output is a halting symbol (e.g. b), the machine halts. (case 2) If it's not a halting symbol (it must therefore be a in your example), it goes back to the location of where it jumped (therefore, "<--"), and reads out the next symbol.