Scribd
Upload
89 views2 pages

Turing Machine Halting Problem

Uploaded by

ashwani456788
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
89 views2 pages

Turing Machine Halting Problem

Uploaded by

ashwani456788
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

Page 1 of 2

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 −


Page 2 of 2

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