The halting problem

Turing showed that there are languages which are accepted by a TM (i.e. type 0 languages) but which are undecidable. The technical details of this construction are quite involved but the basic idea is quite simple and is closely related to Russell's paradox, which we have seen in MCS.

Let's fix a simple alphabet $\Sigma=\{0,1\}$. As computer scientist we are well aware that everything can be coded up in bits and hence we accept that there is an encoding of TMs in binary. I.e. given a TM $M$ we write $\lceil M \rceil \in \{0,1\}^*$ for its binary encoding. We assume that the encoding contains its length s.t. we know when subsequent input on the tape starts.

Now we define the following language

$$L_{\textrm{halt}} = \{ \lceil M \rceil w \mid \textrm{$M$\ holds on \ input $w$.} \}$$

It is easy to define a TM which accepts this language: we just simulate $M$ and accept if $M$ stops.

However, Turing showed that there is no TM which decides this language. To see this let us assume that there is a TM $H$ which decides $L$. Now using $H$ we construct a new TM $F$ which is a bit obnoxious: $F$ on input $x$ runs $H$ on $x x$. If $H$ says yes then $F$ goes into a loop otherwise ($H$ says no) $F$ stops.

The question is what happens if I run $F$ on $\lceil F \rceil$? Let us assume it terminates, then $H$ applied to $\lceil F \rceil\lceil F \rceil$ returns yes and hence we must conclude that $F$ on $\lceil F \rceil$ loops??? On the other hand if $F$ with input $\lceil F \rceil$ loops then $H$ applied to $\lceil F \rceil\lceil F \rceil$ will stop and reject and hence we have to conclude that $F$ on $\lceil F \rceil$ will stop?????

This is a contradiction and hence we must conclude that our assumption that there is a TM $H$ which decides $L_{\textrm{halt}}$ is false. We say $L_{\textrm{halt}}$ is undecidable.