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.