Other Interesting Automata
Contents
Other Interesting Automata¶
There is nothing due on this page. Here is some other interesting automata
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 for it to 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.
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.
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)
Interacting lattice Gases¶
We can generalize our original lattice gas cellular automaton a bit by adding interactions between the atoms. This gives us a more realistic model of a gas. We can also look at how entropy increases in the interacting system and compare it with the entropy in the non-interacting system.
Cellular Automata for Fluids¶
Not only can cellular automata be used to model gases, they can also be used to model fluids. By designing a cellular automaton with simple rules based on a cartoon model of molecular dynamics, you can obtain, from a non-microscopic viewpoint, dynamical behavior that mimics fluid flow. A particular cellular automaton that does this is known at the lattice gas FHP model. The sites of the automaton are arranged on a triangular lattice (with hexagonal symmetry) and each site has six possible states. If you’re bored and feeling ambitious this is really cool and you should try to implement it. An explanation of the FHP model can be found in Section 3.2 of this book.