# 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 Practice Tests

Automata Theory Topics