Scribd
Upload
3 views1 page

Turing Machine Halting Problem

The Turing Machine Halting Problem asks whether a given Turing machine will finish computing an input string in a finite number of steps. The document outlines a proof by contradiction, demonstrating that if a Halting machine exists, it leads to an inverted machine that creates a paradox. Consequently, the halting problem is proven to be undecidable.

Uploaded by

SACOE TIMETABLE
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
3 views1 page

Turing Machine Halting Problem

The Turing Machine Halting Problem asks whether a given Turing machine will finish computing an input string in a finite number of steps. The document outlines a proof by contradiction, demonstrating that if a Halting machine exists, it leads to an inverted machine that creates a paradox. Consequently, the halting problem is proven to be undecidable.

Uploaded by

SACOE TIMETABLE
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

[Link]
Copyright © [Link]

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 H M ’ 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 H M 2 which input itself is constructed as follows −

If H M 2 halts on input, loop forever.


Else, halt.

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

You might also like