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
. 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
we write
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
However, Turing showed that there is no TM which decides this
language. To see this let us assume that there is a TM which
decides
. Now using
we construct a new TM
which is a bit
obnoxious:
on input
runs
on
. If
says yes then
goes into a loop otherwise (
says no)
stops.
The question is what happens if I run on
? Let us
assume it terminates, then
applied to
returns yes and hence we must conclude that
on
loops??? On the other hand if
with input
loops then
applied to
will stop and reject and hence we have to conclude that
on
will stop?????
This is a contradiction and hence we must conclude that our assumption
that there is a TM which decides
is false. We
say
is undecidable.