# What is the contradiction in the proof of the halting theorem?

In the standard proof of the halting theorem, you are asked to assume that a TM_0() exists that takes another TM_1() and a string W and outputs whether TM_1() halts or executes forever right on string W, right? The proof seems to be to assume that such a TM_0() exists. Now a new TM_2() is taken that takes TM_0() as input as halts if TM_0() executes forever, and executes forever if it halts. Now from what I understand such a TM_2() is supposed to mean a contradiction, which in turn implies that TM_(0) is a contradiction. I have trouble understanding how this step in TM_2() constitutes a contradiction. All these steps seem reasonable to me.

You actually have a missing detail on how the machine $$TM_2$$ is defined (and a bit of confusion between $$TM_1$$ and $$TM_0$$). Let's clear this up. You start by the assumption that there is a machine $$TM_0$$ that operates as follows. On input $$x = $$, the machine $$TM_0$$ answers "yes" whenever $$TM_1$$ halts on its input $$w$$, and $$TM_0$$ answers "no" whenever $$TM_1$$ does not halt on its input $$w$$.
Now we define a machine $$TM_2$$. On input $$z = $$ which a description of a machine, denoted $$TM_1$$, the machine $$TM_2$$ runs $$TM_0$$ on $$x = $$ and returns the opposite answer of $$TM_0$$. In words, the machine $$TM_2$$ answers "no" when $$TM_1$$ halts on itself, and answers "yes" when $$TM_1$$ does not halt on itself.
To get a contradiction, consider what happens when we feed $$TM_2$$ to itself as an input. That is, consider the case where the input of $$TM_2$$ is $$z = $$. One of the following holds:
1. $$TM_2(TM_2)$$ = "yes", and so in this case $$TM_0()$$ = "no". Hence, by the definition of $$TM_0$$, $$TM_2$$ does not halt on itself.
2. $$TM_2(TM_2)$$ = "no", and so in this case $$TM_0()$$ = "yes". Hence, by the definition of $$TM_0$$, $$TM_2$$ halts on itself.
All in all, we have that by the two items above that $$TM_2(TM_2)$$ = "yes" iff $$TM_2$$ halts on itself, which is clearly a contradiction to $$TM_2$$'s definition (see the bolded sentence above).