 Proof. Assume the existence of a Turing machine \(H\) deciding the halting problem. We need to show that this assumption leads to a contradiction. The proof mimics Grelling’s paradox. We call a Turing machine \(A\) heterological if \(A\) doesn’t halt on input \(\langle A\rangle\), that is, if \(A\) doesn’t halt when given its own Gödel code as input. Using \(H\), we can construct a Turing machine \(G\) that halts if and only if it is given the Gödel code of a heterological Turing machine as input. \(G\) works as follows: