Does the proof of undecidability of the Halting Problem cheat by reversing results?

Problem Detail: 

I have trouble understanding Turing's halting problem.

His proof assumes that there exists a magical machine $H$ which could determine whether a computer would halt or loop forever for a given input. Then we attach another machine that reverses the output and we have a contradiction and therefore $H$ cannot exist.

My concern is that it seems as though we are saying an answer is wrong because we reversed it. As an analogy, if there is a machine called $A$ such that outputs a correct answer on certain inputs and an incorrect answer on others. Then we attach another machine that reverses the result of $A$ so the combination the two machines have a contradiction with how $A$ is defined. The two machines now generate incorrect answers for inputs that $A$ is defined to output correct answers and outputs correct answers for inputs that $A$ is defined to output incorrect answers. Would this be called a contradiction, and therefore there does not exist a machine that outputs correct answer on some inputs and incorrect answers on others?

Asked By : user27819

Answered By : Luke Mathieson

Short version: The outputs of the machines are not correct or incorrect, they are just contradictory, which proves that the initial machine that decides whether the input machine halts on the given string or not can't exist.

Long version: First we'll sketch the proof (or at least one version of it - there are many).

1. Assume that we have a Turing Machine $\mathrm{HALT}(\langle M\rangle, x)$ that decides whether the Turing Machine $M$ halts on input $x$ or not.
2. Using $\mathrm{HALT}$ we construct a machine $\mathrm{FLIP}(\langle M\rangle, x)$ which uses $HALT$ to check whether $M$ halts on $x$ or not, then does the opposite, i.e. if $M$ halts on $x$, $\mathrm{FLIP}$ loops, if $M$ does not halt on $x$, $\mathrm{FLIP}$ halts.
3. Finally we create a TM $\mathrm{C}(\langle M \rangle)$ (I ran out of good names), which takes the description of a TM and runs $\mathrm{FLIP}$ with input $(\langle M \rangle, \langle M \rangle)$, outputting whatever $\mathrm{FLIP}$ outputs.

It is important to note that as long as the decider $\mathrm{HALT}$ exists, each of these steps is simple to implement; $\mathrm{FLIP}$ just has to use $\mathrm{HALT}$ to check what to do, and $\mathrm{C}$ just duplicates its input to pass to $\mathrm{FLIP}$.

The contradiction arises when we look at what happens when we run $\mathrm{C}(\langle\mathrm{C}\rangle)$. Either $\mathrm{C}$ halts when given itself as input or not. $\mathrm{HALT}$ will decide this:

• If $\mathrm{C}$ halts on input $\langle\mathrm{C}\rangle$, $\mathrm{HALT}$ will say $\mathsf{Yes}$, but then $\mathrm{FLIP}$ will loop, so $\mathrm{C}$ will loop, contradicting $\mathrm{HALT}$.
• If $\mathrm{C}$ loops on input $\langle\mathrm{C}\rangle$, $\mathrm{HALT}$ will say $\mathsf{No}$, but then $\mathrm{FLIP}$ will halt, so $\mathrm{C}$ will also halt, contradicting $\mathrm{HALT}$.

As each of the steps in the construction is clearly sound, we can only conclude that $\mathrm{HALT}$ can't exist; we have constructed a case where no matter what it says, $\mathrm{HALT}$ can't possible decide what to output, i.e. the problem is undecidable. Just to really hammer on the point a bit, $\mathrm{HALT}$ can't exist - that is there can't be a TM that decides the Halting Problem - because there is at least one case we have explicitly constructed where there is no logically possible answer. Remember a decider is not allowed to output the wrong answer and has to output something, but in the case we have constructed, both possible answers are wrong.

Best Answer from StackOverflow

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