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.