Turing Machine Halting Problem - Automata Theory

What is Turing Machine Halting Problem?

Input − A Turing machine and an input string w.

Problem – Whether the Turing machine complete the calculation of the string w in a finite number of steps? Say yes or no.

Proof – Initially you should assume that a Turing machine is used to solve this problem and it will show that it is contradicting itself. This kind of Turing machine is called as a Halting machine which produces a ‘yes’ or ‘no’ in a finite amount of time. Incase if the halting machine completes in a finite amount of time, the output will be yes’, otherwise it will be ‘no’. Below mentioned block diagram of a Halting machine is −


Now we will design an inverted halting machine (HM)’ as −

  • If H returns YES, then loop forever.
  • If H returns NO, then halt.

Below mentioned block diagram of an ‘Inverted halting machine’ −


After that a machine (HM)2 which input itself is constructed as follows −

  • If (HM)2 halts on input, loop forever.
  • Else, halt.

After this we got a contradiction then the halting problem is undecidable.

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics