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?