Halting problem (3) - Proof tracing in "The Emperor's New Mind"
There are two versions of the popular proof of the "haling problem": one based on the liar's paradox and the other based on the Cantor’s diagonisation. The academic claims that the halting problem and its proofs are originated from Turing's 1936 paper, which is highly questionable, … Roger Penrose gave an accessible presentation of the proof of the halting problem based on the Cantor’s diagonisation in The Emperor's New Mind , and I excerpt the relevant content as follows (p.59-64) : A natural question arises: how are we to decide whether or not any particular Turing machine (when fed with some specific input) will ever stop? … So, is there some algorithmic procedure for answering the general question - the halting problem - completely automatically? Turing showed that indeed there is not. His argument was essentially the following. We first suppose that, on the contrary, there is such an algorithm. Then there must be some Turing machine H which 'dec