Scribd
Upload
335 views2 pages

Turing Machine Halting Problem

Uploaded by

gbalu0061
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
335 views2 pages

Turing Machine Halting Problem

Uploaded by

gbalu0061
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Turing Machine Halting Problem

Input − A Turing machine and an input string w.

Problem − Does the Turing machine finish computing of the string w in a finite number of
steps? The answer must be either yes or no.

Proof − At first, we will assume that such a Turing machine exists to solve this problem
and then we will show it is contradicting itself. We will call this Turing machine as a
Halting machine that produces a ‘yes’ or ‘no’ in a finite amount of time. If the halting
machine finishes in a finite amount of time, the output comes as ‘yes’, otherwise as ‘no’.
The following is the block diagram of a Halting machine −

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

If H returns YES, then loop forever.

If H returns NO, then halt.

The following is the block diagram of an ‘Inverted halting machine’ −

Further, a machine (HM)2 which input itself is constructed as follows −

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


Else, halt.

Here, we have got a contradiction. Hence, the halting problem is undecidable.

You might also like