Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Calculus, linear algebra, discrete mathematics, logic and proof, and models of computation / 10 / c / Solution

The halting problem asks, given the encoding $⟨M,w⟩$ of a Turing machine and an input string, whether that machine eventually halts on that input. Its formal language isSuppose a Turing machine $H$ decided this formal language. Construct another Turing machine $D$ that, on an input encoding $⟨M⟩$, runs $H$ on $⟨M,⟨M⟩⟩$. If $H$ answers that $M$ halts on its own encoding, $D$ enters an infinite loop. If $H$ answers that $M$ does not halt, $D$ halts. Handling malformed encodings by immediate rejection makes $D$ well-defined on arbitrary strings.

Now run $D$ on its own encoding. If $H$ says that $D$ halts, the construction makes $D$ loop; if $H$ says that $D$ does not halt, the construction makes $D$ halt. Either answer contradicts the assumed correctness of $H$. ThereforeThe contradiction concerns a decider that must give a correct terminating answer for every encoded machine and input. Simulating $M$ does detect a halt when one occurs, but cannot in general certify that a running computation will continue forever.