So even by defining such a simple machine
one can start asking all sorts of interesting

questions such as
What is the typical behaviour of a Turing

machine?

How to prove (non-)universality results?

How many universal Turing machines there are?

How small can they be?

How fast they can compute?

How can they be implemented and physically
realized?

Are digital computers Turing machines?

Can we do better (faster/more powerful) than
Turing machines?

Each of these questions deserves a full lecture
by themselves but let me quickly cover a couple

of them in the next slides because it helps
my case to convey the value of the Turing

machine model and why if there is anything
you should well rather well in theoretical

computer science is this model and its most
implications.

So let me start by the first question on the
behaviour of Turing machines.

And this is actually a game that some people
even researchers study, the question that

drives the game is to find the Turing machine
that, given a number of symbols and states,

takes the longest computing time to halt among
all the machines of the same size that halt.

A similar question is a machine that prints
more 1s on its tape, among all the machines

in of the same size, such a Turing machine
is called the Busy Beaver, you know because

it looks very busy, more than any other of
the same size.

Fixing the number of states and symbols means
that the number of Turing machines is finite

so for small states and symbols one can go
almost one by one trying to figure out the

Busy Beaver machine, and some of such machines
are known, here is a table of some of them,

but one can see how fast the largest number
grows and, more importantly, how fast the

number of Turing machines grow in order to
continue looking for the next Busy Beaver.

The Busy Beaver is an example of an uncomputable
problem because of the halting problem.

You see how it goes, if you were able to find
all Busy Beavers you would know whether a

Turing machine will halt or not only by looking
at its number of states and symbols but we

know this is not possible because of the undecidability
of the Halting problem that we have explored

before.

I myself have a conjecture about Busy Beaver
Turing machine, I think they are natural candidates

for Turing universality because they are non-trivial
Turing machines and as I will explain in the

next slides, it is quite easy to construct
universal Turing machines.

This is a nice visualisation I created, related
to my own research interests, that shows the

behaviour of a typical finite set of Turing
machines for a given number of states and

symbols.

Each dot represents a small Turing machine
with 2 states and 2 symbols of which there

are 10 thousand.

The darker the dot the longer the machine
takes to halt.

White dots are machines that never halt, and
red dots are the Busy Beavers.

Now you can see that most Turing machines
either never halt or halt quickly, and only

a few do a lot of work and halt.

So this gives you an idea of the typical behaviour
of a Turing machine for an empty tape.

Actually, I won a prize for this image not
only because it shows a slide of the computational

universe but also because it is doing so in
a clever way.

Each dot is arranged according to a space-filling
curve called a Peano curve that has the advantage

to preserve as much as possible in 2 dimensions
the linear distance between Turing machines

that are close to each other in an enumeration.

Another question is how one can find or construct
universal Turing machines in general.

Given a Turing machine how one proves universality
or non-universality?

Well, if one can decide whether a machine
will always halt or not, then that machine

is said to be decidable.

In some cases this is very easy to do.

Here the rule delta sends any input to the
halting state 0 so we know that the machine

halts for any input and therefore is decidable.

If a machine is decidable then it cannot be
universal.

However, proofs of universality are much more
difficult and a common way to prove that a

model is universal is by showing that one
can construct a universal machine in that

model the emulates a universal Turing machine.

So by chaining to universal models, one proves
universality.

So if not all Turing machines are universal,
which one are and which are not?

This plot with number of states on the X axis
and number of symbols or colours on the Y

axis, it turns out that

with extremely few elements of both, one can
build a universal Turing machine.

Turing’s original universal machine used
at least 18 states but we know today that

universal Turing machines can be as small
as having only 5 states and only 2 symbols.

And under special even with only 3 symbols
or colours and 2 states one can build a universal

machine.

The precise boundary is yet not completely
known but known results are on this plot with

every dot showing a machine that is universal
and the coloured ones are universal in a slightly

different way.

We know for example that no universal Turing
machine exists with only 2 states and 2 symbols

and that Claude Shannon himself proved that
one can always exchange symbols for states

so there is some sort of nonlinear symmetry
among the machines on one side and the other

of these axes.