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

Problem Detail: 

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?

Asked By : StudentsTea

Answered By : StudentsTea

Here is how a logician might approach the problem:

$h(M,i)$ is the general case solution to the Halting Problem by definition.

$(1)$ $h(M, i)$ must be able to determine whether or not $M$ halts for all $M$ ( i.e. an unrestricted set of $M$ ).

$p(M)$ is an element in $M$.

$(2)$ The following statements are equivalent:

• $p(M)$ halts if and only if $h(M,M)$ returns $false$
• $p(M)$ halts if and only if $p(M)$ doesn't halt

$(3)$ Additionally, the following statements are equivalent:

• $p(M)$ does not halt if and only if $h(M,M)$ returns $true$
• $p(M)$ does not halt if and only if $p(M)$ halts

Both $(2)$ and $(3)$ are contradictions.

$h(M,i)$--the general case solution to the Halting Problem--cannot properly determine whether or not $p(M)$ halts, contradicting $(1)$. Therefore, the general case solution for the Halting Problem does not exist.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29428