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

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?

Answer 1

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.

Answer 2

You’re discussing two different meanings of “contradict”.

In your analogy, the machine A and its flipped modification contradict each other just in the sense that their outputs are always different. (For instance, they might implement two test functions on integers, “x ≤ 5?” and “x > 5?”) That’s certainly one thing “contradict” can mean in everyday usage, but it’s not what is meant by it in logical proofs.

In logical proofs, it means something stronger: something that’s simply impossible. E.g. a function that returns “true” on all inputs more than 5, and “false” on all inputs less than 10 — that’s contradictory in this stronger sense, because for, say, 7, its output would have to be both “true” and “false”, but those are not the same. Turing’s argument shows that the halting program is contradictory in the stronger sense: assuming it leads to something that’s impossible, or already known to be false.

Answer 3

Here is another proof that the halting problem is undecidable. We say that a program outputs a string $x$ if it halts and outputs $x$. (If the program never halts, then it doesn't output any string.) Define $f(n)$ to be the length of the longest string which is output by a C program of length at most $n$.

Suppose that the halting problem were decidable. Then $f(m)$ can be calculated by a C program:

On input $m$, run over all halting C programs of length at most $m$, and determine their output; return the length of the maximal output.

That means that for each $m$, we can write a program $P_m$ that outputs $f(m)+1$ zeroes. What is the length of $P_m$? There is a fixed C program template, with a placeholder, that implements $P_m$; the placeholder should be filled with the constant $m$. Specifying $m$ takes $|m|$ characters (here $|m|$ is the length of the decimal representation of $m$), where $|m| \approx \log_{10} m$. The template takes some fixed number $T$ of characters, and so the length of $P_m$ is $T + \log_{10} m$. If we choose $m$ large enough ($m=2T$ would do), we will have $T + \log_{10} m \leq m$, and so $f(m)$ is at least the size of the string output by $P_m$, i.e., $f(m) \geq f(m) + 1$. We have reached a contradiction.