Notice that a Turing machine is just a computer program like any other.
So now one may ask whether all problems that can be written as a computer program can be
computed or solved by a computer like a Turing machine.
For example, have you ever wondered if one can avoid this kind of messages on your computer?
What about this one!
The scary blue screen of some versions of Microsoft Windows telling you that your computer
just crashed.
Well, it turns out that they cannot be completely eliminated, it turns out that these kind of
problems are not solvable or computable.
If you want to ask questions about the behaviour of Turing machines or computer programs in
general.
And Alan Turing himself showed this precisely to show that David Hilbert’s hope to automatise
mathematics was impossible.
So imagine we were able to know when a computer program will never halt, like the case in
which you get a message from your computer telling you that there is a problem running
a program.
In other words, we could build a Turing machine U that accepts as input the description of
another machine M and then U halts and tells you that M does not halt if M does not halt,
or U does not halt if M halts.
But this may lead to a contradiction if we replace M with U itself, so basically U is
getting a description of itself!
So if U halts then U does not halt and U does not halt if U halts!
So this means that our assumption was wrong and indeed it is not possible to know in general
whether a Turing machine M will ever halt or not.
So this somehow justifies why companies cannot write completely flawless software.
And what we just did has the fancy technical name
of Undecidability of the Halting Problem.
And this a simplified answer to Hilbert’s question related to questions in mathematics
because mathematical problems are like computer programs.
But the positive outcome we were talking about at the beginning of the lecture has outstanding
consequences and is the following.
Before the era of modern computers one may have thought to require a different machine
for different tasks, you needed a typewriter if you wanted to type a novel, you needed
a radio device if you wanted to listen to music, you needed a phone if you wanted to
reach someone.
But these days all that and much more is performed by a single machine.
Isn’t it amazing?
In other words, there is one machine for everything, and that property of machines is called Turing
universality.
So in the exercise we did to prove the undecidability of the Halting problem we encoded the description
of the Turing machine M as an input to the machine U.
Well, this was not an obvious trick, one would need to prove that indeed one can do such
a thing and that by doing so U can follow the instructions of M to behave like M. And
that is what Alan Turing did.
He proved by writing such a universal Turing machine, that given any Turing machine one
can encode it as the input on a tape for a special kind of machine that can emulate all
other machines.
And this is these days kind of obvious because it is what we do all the time.
We reprogram our computers to behave in different ways when we open an application and this
is what Turing understood and gave us!
He showed us that there were no fundamental differences other than operational between
programs and data because one can be written as the other.
So how difficult is to build or actually write a Universal Turing machine?
Well, it is actually quite easy!
Here is an implementation of one in C++ language written by Alex Stangl for a contest that
I organised a few years ago.
You can see how small, do not try to understand it if easily because the code is quite obfuscated
as the contest purpose was to write the smallest possible Turing machine in every programming
language.
And this is Turing’s original universal Turing machine!
Isn’t it amazing to look at the history of computer science?
It is a tricky machine because some of these labels are not traditional Turing machine
states but subroutines that Turing defined in his paper.
E, for example, stands for Erasing.
If you want to know more about it you can go to my blog at this URL below.