Other Interesting Automata#
There is nothing due on this page. It is just additional examples and information about automata.
There are two common applications of cellular automata. In the one case, they are often used as minimal models for physical phenomena. We saw this in the previous page where we used a cellular automata as a simple model of a diffusing gas and from this computed the entropy and approach to equilibration.
Another interesting application is to show that cellular automata are able to build universal classical computation - i.e. you can program a celluluar automate which simulates any computation that you can do on your macbook. This really speaks to the fact that computing is a universal phenomena - from almost any simple physical rules, we can build devices which compute anything.
These things are not completely unrelated. The Church-Turing thesis tells us that any physical computing device can be simulated by any other physical computing device. We will discuss a modified form of this thesis - the modified church Turing thesis - which indicates that any physical computing device can be simulated by any other physical computing device without a significant loss of efficiency. It turns out that quantum computers are one of the only known counterexamples of this.
Universal Computation#
We’ve seen that cellular automata can produce fairly complicated behavior. In spite of that, you’ve managed to write a simple program on your laptop that simulates this behavior. Because you can do such a simulation, this means your laptop is at least as computationally powerful as a cellular automata. This is called a reduction.
The set of problems that your laptop can solve are called computable problems. Your laptop is a type of machine called a Von Neumann machine (it has RAM, CPU, etc.) There is another class of machines called Turing Machines. Turing Machines have
a long scroll of paper (a “tape”)
a head which sees one letter on the tape
and a bunch of rules like - if you see a `W’ at the head move the tape to the right - if you see a ‘V’ at the head, write instead a ‘W’ where the head is
Turing machines (invented by Alan Turing) are also able to compute everything your laptop can compute (and visa versa). Turing Machines and your laptop are both equally as powerful with respect to the things they can compute.
It is then an interesting question to ask how computationally powerful cellular automata are? Naively, one might think with such simple rules that there are things a laptop can compute but a cellular automata can’t. The answer turns out to be surprising. Any problem your laptop can solve, cellular automata can also solve. In fact, given just the rules for Conway’s game of life, and the right initial starting configuration for the grid, you can simulate a program running on your laptop. Cellular Automata and your laptop are equally powerful with respect to what can be computed.
This suggests that everything classical in the universe has this property and this is generically true. Put together a sufficiently non-trivial set of local deterministic rules (cellular automata, billiard balls bouncing around etc.) and we get something that can both be simulated and simulate anything in this class. When we get to the section on quantum computing, we will ask this question again about the quantum world.
Later on we will also talk about not only what is computable but also how fast things can be computed. This falls under the realm of complexity theory.
The fact that billiard balls and cellular automata and laptops being equally powerful computationally has some interesting consequences.
Unanswerable physics questions
One implication of this is that there are unanswerable physics questions even in a deterministic universe. This follows from the fact that you can’t solve the Halting problem. Notice this inability to predict has nothing to do with chaos. This is true even on a cellular auomata where everything is binary and there are no precision issues with the initial conditions.
Secondly, we can’t fast-forward time. For many problems if we want to know something about the future, we have to essentially simulate the future. This goes under the name no fast-forwarding.
A question of chaos?
Chaos tells us about things that are unpredictable because of arbitrary sensitivity to initial conditions. This is fundamentally different then the unanswerable questions above which are discrete and have no initial-condition issues.
Billiard Balls
You might wonder if Billiard Balls can also be universal computers. In fact, they can. You can just make collisions of the billiard balls (with mirrors) act like gates. See [Margolus, N. H. (1988). Physics and computation (No. MIT/LCS/TR-415). MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE.] for a nice discussion of this.
Turing Tumble
There is a children’s toy, Turing Tumble where one can do universal quantum computational with marbles.
One-dimensional automata#
Various other interesting cellular automata rules exist. Wolfram has enumerated many of these one-dimensional automata (which you can visualize actually the full space-time evolution in 2d). Of particular interest are Wolfram rule 30 and rule 110 (also universal)
The game of life#
Cellular automata consists of a grid in space where each pixel on the grid is in some state (maybe black or white). Throughout much of this course, the first question we will often ask ourself about a simulation is what describes its state - i.e. what do I have to store in my computer. Then there are some simple rules which tell you how to change the state of your automata.
The most popular cellular automata is John Conway’s game of life. In this cellular automata, each square is either black or white. Notice that on a square lattice, every cell has eight cells around it. The rules are pretty simple:
If you are black and there are fewer then 2 black squares around you, you become white.
If you are black and there are more then 3 black squares around you, you become white.
If you are black and there are exactly 2 or 3 black squares around you, do nothing.
If you are white and there are exactly 3 black squares around you, become black.
In spite of the simplicity of the rules that there are various (in fact arbitrary) complicated behaviors which can happen.
Unsurprisingly, the game of life is also a universal automata.
There is a proof of this here: https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor
What this means is you should be able to program anything - say a game of Tetris - just using the simple rules of the game of life above. Here is an amazing example where people actually did so: