So with so many Turing machines and rules that can be built from states and symbols,
something useful to do is to identify each Turing machine with a number.
It should not be any number, ideally it should be a unique one and no Turing machine should
have 2 numbers or be repeated in any trivial way.
That is called an enumeration.
An enumeration can deal with an infinite number of objects such as Turing machines, given
that the number of Turing machines implementing a computer program is infinite.
The other side of the coin is that of a search, because once we are able to enumerate and
identify every Turing machine one can search and explore the whole space in an exhaustive
and systematic fashion.
The basic idea of an enumeration and of an exhaustive search is to transform a countable
set, possibly infinite into a totally ordered set, that means that we can always know which
item is first and which comes before and after.
The basic requirement for an enumeration is to device a strategy to (1) avoid repetition
or redundancy, (2) not miss any valid element by, for example, falling into infinite branches.
One useful way to see an enumeration even for non-trivial objects such as Turing machines
is as a graph and the way we can traverse it.
For example, a non-effective enumeration or exhaustive search is what is known as the
depth-first strategy or DFS:
Because it would try to go deeper and deeper in a single branch of the tree before exploring
other branches:
But the so-called breadth-first search goes a level at a time hence a good strategy to
enumerate or count objects:
The search is said to be exhaustive because it is guaranteed to go through all the elements
and for any given number of elements it will do so in finite time.
Many sets are countable: finite sets, the sets of natural numbers, integers, rational
numbers, computable numbers, but some others are not, for example, irrational numbers.
There exist sets for which no effective enumeration exists: the set of real numbers (and therefore
non-rational numbers), non computable numbers, (ML) random numbers.
The advantage of an exhaustive search is that the details on the enumeration are irrelevant,
one is guaranteed to cover the whole space.
The following is an example of an enumeration by length and lexicographical order
Let's say we consider the set of all possible strings containing the letters A and B, one
way to see these sets is as follows, we have the set of all strings of increasing length
using only A :
And then the set of all the strings of increasing length using only B:
Then the set of all strings of increasing length that start with B followed by As.
and so on.
The number of sets is infinite and before exhausting one it would be impossible to get
to the next one.
What we can do to make an enumeration is to alternate between these sets as follows.
We start with all the strings of length 1 hat contain both A and B, then all the strings
of length 2, and so on.
In this fashion, we can reach any given string with As and Bs of any length in finite time,
traversing all the ones that are of shorter length, unlike the way in which we were visualizing
the first sets.
To this way of intercalating objects is sometimes called dovetailing in Computer Science.
For any number of countable sets it is still possible to come up with an enumeration because
the sum of countable sets is a countable set:
This is another example with mathematical logic of propositional calculus.
If we want to enumerate all possible formulae with the main Boolean operators we can start
in the same fashion as for the case with strings, listing the sets individually:
and then producing a total order of those sets by taking first the formulae up to certain
size and exhaust it, and then take the next formula length and so on:
This means that the number of Boolean formulae are countable.
This kind of enumerations can be sometimes useful.
For example, by means of an enumeration and an exhaustive search of propositional logic
like this one, Stephen Wolfram found the single shortest axiom system equivalent to Boolean
algebra, in other words, it can generate all other formulae and all possible truth tables.
The result can be found on page 809 of Wolfram's A New Kind of Science book:
In another project that also led to an interesting application, I took Wolfram's project to the
next level and I devised a way to enumerate all the formulae of first order logic.
Most of mathematics, like calculus, analysis, geometry, topology and algebra can be written
in this language of first order logic.
I proved that, with the use of an automatic theorem prover, the length of the proofs found
were distributed in a similar fashion to the distribution of halting times for Turing machines,
thus establishing an interesting connection that helps to determine when to stop a mathematical
proof when using an automatic theorem prover.
A useful enumeration in our course will be that of Wolfram's for elementary cellular
automata.
Remember that a cellular automata is another type of computing machine just as a Turing
machine.
The main difference is that a cellular automata runs in parallel, but essentially they are
the same.
Indeed, cellular automata and Turing machines have exactly the same computational power,
meaning that whatever you can compute with one you can also do it in the other, similarly
to computer languages, meaning that whatever you write in Java you can also write it in
C++.
A one-dimensional cellular automaton runs on a tape just as a Turing machine, and then
applies a global rule that dictates how to update the cells on the tape.
Elementary cellular automata are binary one-dimensional cellular automata whose updating function
takes the value of every 3 cells to update the next one.
Just like we saw before:
So starting from the top, we take the rule and update the bottom cell according to the
values of 3 cells at a time.
Here are all the possibilities in which 3 different cells can appear, there are exactly
8, which is 2 to the power of 3 possible cases.
See how for 3 white cells, the next centre cell remains white, but for the case of white,
white, black, it applies the rule corresponding to that case and colours the next central
cell black.
So from all the rule cases the rule can either print a 1 or 0 in the next central cell, which
means that we can have 256 possible combinations, that is 2 binary options to the power of 8
which was the possible of local rules that take into consideration 3 cells.
Now we can see how elementary cellular automata can be enumerated.
We take the 8 local rules and then assign all possible combinations of sending 3 cell
values to a new binary value, either black or white.
We can then enumerate by the number in binary represented by the red cells in the rule icons,
so rule 5 will be five in binary, and so on, representing the 256 cases.
So once the space of all elementary cellular automata are properly enumerated we can conduct
an exhaustive search and study the behaviour of these computer programs.
So we saw some sort of fundamental predictability limit in the halting problem for computer
programs.
In other words, for computer programs that halt such as Turing machines, we cannot device
an algorithm to determine when a computer program will halt in advance, and when it
does not halt we can never know, not even running it, because may keep waiting forever.
But what about other weaker forms of predictability?
It turns out that very little can be said about a computer program before running it,
and even after running it.
Let's see some cases:
In the case of elementary cellular automata rules with number 0, 32, 160, 250 or 254,
to mention some examples, the rules are very simple, like this one:
Whatever they are fed, they quickly settle into some trivial pattern.
Here is another rule starting with some a random initial condition:
Some others rules show other patterns, such as periodicity and fractality:
Some others, however, look random for many purposes.
In this category are rules such as rules 22, 30, 150, 182, 80, 105:
Even starting from the simplest initial condition such as a black cell, these examples of cellular
automata produce some statistical randomness passing very sophisticated tests for randomness:
Other cellular automata display really complex behaviour, including this one with rule 110
that was proven to be Turing universal, meaning that one can reprogram it to behave as any
other computer program.
Indeed, capable in principle to run Microsoft Windows or the game of Minecraft:
Similar behaviour can be found in larger cellular automata, such as these cases:
Elementary cellular automata can even display features similar to physical phenomena, such
as particle collision.
Here is an elementary cellular automaton with rule 219 that annihilates every 2 particles
that touch each other.
It reminds me the Missile Command game from Atari.
Some rules are very sensitive to initial conditions, reproducing chaotic behaviour that we will
study later in the course.
For example, rules 90, 126 and 22 are very sensitive and sometimes behave very orderly
and sometimes produce random-looking behaviour:
Even simple questions such as when rule 126 will produce some sort of giant triangle in
its evolution is hard, if not impossible to answer.
The same richness can be found in many other spaces of simple programs with more colours:
So we need very powerful tools to study the behaviour of even the simplest programs and
we will use both the knowledge about the behaviour of these programs and those tools to study
programs to study the world and natural phenomena such as living organisms and molecular processes.