How is Turing's Solution to the Halting Problem Not Simply "Failure By Design"?

I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer.

Here is my understanding of the Halting Problem:


Let $M$ be the set of all Turing Machines.


Let $i$ be the set of all inputs for all the Turing Machines in $M$.


Let every element in $M$ be an element in $i$.


Let the boolean values $true$ and $false$ be elements in $i$.


Let $h(M,i)$ be a function that returns:

• $true$ if and only if $M(i)$ halts

• $false$ if and only if $M(i)$ does not halt

Let $p(M)$ be a Turing Machine in $M$ that:

• calls $h(M,M)$

• halts if and only if $h(M,M)$ returns $false$

• doesn't halt if and only if $h(M,M)$ returns $true$

What happens when we call $p$ by passing $p$ to itself, $p(p)$?

The part I take issue with is implementing $p(M)$ so that it will not halt when $h(M,M)$ is $true$. My gut understands this approach as follows:


Given a method $h()$ that works, and a method $p()$ designed to break $h()$, when we combine these methods to build a machine, that machine is broken.

I understand proof by contradiction is a valid approach to problem solving in formal logic, but this particular application of proof by contradiction seems flawed somehow.

What am I missing?

In what follows, I'll distinguish a machine $M$ from its description, denoting the description of $M$ by $\langle M\rangle$.

Specification of the halt tester program, $H$


$H$ takes as input a pair $(\langle M\rangle, i)$, where $\langle M\rangle$ is the description of machine $M$, and $i$ is the input required by $M$.


$H$ halts on any input pair $(\langle M\rangle, i)$ and returns the correct answer, namely:


$H(\langle M\rangle, i)$ returns true if and only if $M$ halts on input $i$.

Now, assuming that there is such a machine $H$, we can use $H$ as a subroutine to construct a program $P$ as follows:

Specification of the "perverse" program $P$


$P$ takes as input a description, $\langle M\rangle$, of a machine $M$.


$P$ works correctly on any input $\langle M\rangle$, namely


$P(\langle M\rangle)$ halts if and only if $M$ doesn't halt when given input $\langle M\rangle$.

The key to this argument is that if we can define a machine $H$ that satiffies the specification above, then we can build a machine $P$ that satisfies the second specification.

However, $P$, when given $\langle P\rangle$, exhibits impossible behavior,

$\qquad\qquad\qquad P(\langle P\rangle)$ halts if and only if $P(\langle P\rangle)$ doesn't halt.

So $P$ fails to meet its second requirement on at least one input and consequently it must be the case that $H$ cannot satisfy its requirement, so consequently we cannot make $H$ as specified.

Now $H$ might very well behave as specified on lots of inputs $(\langle M\rangle, i)$, but the point is that no halt tester can be built that works on all possible inputs.

StackExchange Computer Science Q#29428, answer score: 11