I have trouble understanding Turing\'s halting problem. His proof assumes that t
ID: 649286 • Letter: I
Question
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?
Explanation / Answer
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).
Assume that we have a Turing Machine HALT(?M?,x) that decides whether the Turing Machine M halts on input x or not.
Using HALT we construct a machine FLIP(?M?,x) which uses HALT to check whether M halts on x or not, then does the opposite, i.e. if M halts on x, FLIP loops, if M does not halt on x, FLIP halts.
Finally we create a TM C(?M?) (I ran out of good names), which takes the description of a TM and runs FLIP with input (?M?,?M?), outputting whatever FLIP outputs.
It is important to note that as long as the decider HALT exists, each of these steps is simple to implement; FLIP just has to use HALT to check what to do, and C just duplicates its input to pass to FLIP.
The contradiction arises when we look at what happens when we run C(?C?). Either C halts when given itself as input or not. HALT will decide this:
If C halts on input ?C?, HALT will say Yes, but then FLIP will loop, so C will loop, contradicting HALT.
If C loops on input ?C?, HALT will say No, but then FLIP will halt, so C will also halt, contradicting HALT.
As each of the steps in the construction is clearly sound, we can only conclude that HALT can't exist; we have constructed a case where no matter what it says, HALT can't possible decide what to output, i.e. the problem is undecidable. Just to really hammer on the point a bit, 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.