1
$\begingroup$

enter image description here

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.

$\endgroup$
1
$\begingroup$

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 = <TM_1, w>$, 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 = <TM_1>$ which a description of a machine, denoted $TM_1$, the machine $TM_2$ runs $TM_0$ on $x = <TM_1, TM_1>$ 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 = <TM_2>$. One of the following holds:

  1. $TM_2(TM_2)$ = "yes", and so in this case $TM_0(<TM_2, TM_2>)$ = "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(<TM_2, TM_2>)$ = "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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.