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)₂ which input itself is constructed as follows −

• if (hm)₂ halts on input, loop forever.
• else, halt.

here, we have got a contradiction. hence, the halting problem is undecidable.