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 $\mathrm{HALT}(\langle M\rangle, x)$ that decides whether the Turing Machine $M$ halts on input $x$ or not.
- 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.
- 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.