undecidability of halting

Question

In the "Halting Problem" lecture, the Prof. Shai Simonson introduced a magic trick to use the fact that there exists no TM that accepts all other TM that accept themselves to prove that the halting problem is undecidable. There he asked to change the algorithm to alternate the answer i.e if the answer is yes change it to no and vice versa. Then he proved that the halting problem is undecidable. I kind of didn't get his magic trick for the proof. It would be great if somebody can shed some light on it. Thanks!

https://www.youtube.com/watch?v=e9zzY7uqT8g

Answer 1

'magic trick' is a big word. Anyway, the 'trick' is easy to explain.

So the question is:

Is there a Turing machine (a 'Halting Macine') that can take a description of any Turing machine M, and input I on its input, and that can decide whether machine M with input I will halt?

The answer is No.

To prove that there is no such 'Halting Machine', you do a proof by Contradiction:

If there is a Halting machine, then you expand that machine by two little bits of code:

First, you have a 'Copy' machine that simply produces two copies of its input on its output.

Second, you have a 'Negator' machine that takes the output of the Halting machine, and does the following:

If the Halting machine says that M with I halts, then the Negator machine will go into some infinite loop, i.e. it will not halt.

If the Halting machine says that M with I does not halt, then the Negator machine will do nothing (and thus the Negator machine will halt)

Now, both the Copy machine and the Negator machine are easily shown to be implementable by a Turing machine. Thus, if there is a Halting machine, we can create a new Turing machine $Q$ that take as input a description of some machine $M$, runs the Copy machine, then the Halting machine, and finally the Negator machine.

Now, since $Q$ is a Turing machine itself, we can feed the description of $Q$ into $Q$ itself. So, the Copy machine will take the description of $Q$, and make two copies of it, and pass that to the Halting machine. So, the Halting machine has on its input $Q$ and $Q$, and so the Halting machine will try to figure out whether machine $Q$ with input $Q$ will halt or not. Fibally, oince the Halting machine has made its decision, the Negator machine will do its thing.

But note:

If we assume that $Q$ with input $Q$ halts, then the Halting machine will say exactly that on its output. But, the Negator machine was set up in such a way that it will then go into an infinite loop. So: If $Q$ with input $Q$ halts ... then it does not halt!

OK, so what if $Q$ with input $Q$ does not halt? Then the Halting machine will say so, and then the Negator machine will do nothing, and hence the whole machine $Q$ will halt. So: If $Q$ with input $Q$ does not halt ... then it does halt!

OK, but now we have a contradiction: machine $Q$ with input $Q$ will halt if and only if it does not!

OK, so where did things go wrong? In our assumption that we could create such a Halting machine .. apparently that is impossible!

Here is a cute video that goes through the same proof:

https://www.youtube.com/watch?v=92WHN-pAFCs