The Halting Problem -- why do we do the opposite?

167 Views Asked by At

I don't really get why testhalt doesnt exist based on the proof that some program, ie turing, called on testhalt does the opposite of testhalt. Below is a definition for testhalt enter image description here And one for turing.

enter image description here

How come we absolutely must, in turing, do the opposite of testhalt? (meaning loop if testhalt halts, for example)

1

There are 1 best solutions below

0
On

The point isn't that $\mathsf{TURING}$ does the opposite of $\mathsf{TESTHALT}$, but rather that - when fed a judiciously chosen input - it does the opposite of itself. Since this is blatantly impossible, $\mathsf{TURING}$ can't exist and therefore $\mathsf{TESTHALT}$ can't exist either.

Specifically, consider what happens when we feed $\mathsf{TURING}$ its own index $\tau$. We get that $\mathsf{TURING}(\tau)$ halts iff $\mathsf{TESTHALT}(\tau,\tau)$ says "no" (by definition of $\mathsf{TURING}$) iff $\mathsf{TURING}$ does not halt on input $\tau$ (by assumption on $\mathsf{TESTHALT}$). This self-contradictory behavior ("I halt on input $\tau$ ifff I don't halt on input $\tau$") is what concludes the argument.