Q: What is Busy Boxes? Is it a game? A research project? What?

A: Busy Boxes (BBX) is an implementation of the 3D reversible cellular automata developed by Ed Fredkin and Daniel B. Miller in their 2005 paper, Two State, Reversible, Universal Cellular Automata In Three Dimensions. A preprint is available here.

We have just posted a more recent paper to the arXiv, entitled Circular Motion of Strings in Cellular Automata, and Other Surprises. The paper includes informational links back to this website.

Q: What is the point? Are there any goals, or levels?

A: There are open questions about what the BBX algorithm is capable of. In particular, we would like to know if BBX is capable of Universal Construction, in the sense outlined by Von Neumann in The Theory of Self-Reproducing Automata (1966). In simple terms the question is, can you build a machine in BBX that can build another machine similar to itself?

Before we answer that question, we will need to answer a number of smaller but interesting questions. While we know that BBX is capable of Universal Computation, it's not at all clear how to build practical examples of effective computation within a finite implementation. As discussed in the paper, we can route information, and perform rudimentary logic operations. However, it is far from obvious how, in practical terms, useful computation can be performed within a limited, finite lattice. Presumably, reversible logic would be used; however, it is interesting to note that while our universe is based on reversible physics, we generally build computation machines using traditional, irreversible Boolean logic. The extra information created by these operations is turned into heat (which is why faster computers need bigger fans!)

Q: What's all this about reversibility? Isn't this just like the Game Of Life, only in 3D?

A: The Game Of Life (GOL) and BBX are both cellular automata, and both have been shown to be Turing complete, which means that you can build computers inside the game that can process information in arbitrary ways. The interesting thing about BBX and related algorithms (such as the Billiard Ball computer, implemented as a Cellular Automata) is that they have a set of rules that is reversible, meaning that you can reverse the flow of time and recover the exact states that you had before. You can't do that in the GOL (think of a single cell which dies; reversing time, it's just a blank cell forever.)

Reversibility introduces some very interesting properties, including a number of things which seem intriguingly related to physical laws that we observe in our own universe (the laws of physics are also reversible.) For instance, because BBX is reversible, if we run it in a finite space (this implmentation uses a 3D lattice of 24 * 24 * 24, or 13,284 cells), we know that eventually, any pattern will repeat itself. This means that it is impossible (in a finite implementation of BBX) to build a structure (from within the game) that lasts forever. That's how we knew that this would eventually come to this (it takes about 60,000 generations!) We believe this relates in a deep way to entropy, the laws of thermodynamics, and the apparent asymmetrical nature of time.

We can also use reversibility to prove that, for example, two 2-cell gliders cannot combine to create one 4-cell glider. If they could, then we would be able to reverse the flow of time, and the 4-cell glider would spontaneously break up into two 2-cell gliders. We can see clearly that the 4-cell glider is stable if it doesn't interact with any other cells, so this is impossible. However, three 2-cell gliders can combine to make a 2-cell and a 4-cell glider, like this.

Q: So what are the rules?

A: The rules of this Cellular Automata are as follows:

• Play takes place on a 3D Cartesian lattice of cells.
• Each cell in the lattice is either odd or even, depending on whether the sum of the three coordinates specifying that cell's location in the lattice is odd or even.
• Cells are either 1 or 0. 1 cells are shown as red if they are even, or blue if they are odd. 0 cells are not shown.
• There are six phases in the evolution of the CA, numbered 0 to 5. During even phases, only even cells are operated on. During odd phases, odd cells are operated on.
• During phase 0 and 3, the planar rule is applied to the XY plane. During phase 1 and 4, it is applied to the YZ plane. During phase 2 and 5, it is applied to the ZX plane.
• The planar rule is this: for each diagonally situated pair of cells on the plane, if a 1 exists at either of the pair's knight's move positions, the value of the two cells in that diagonal pair is swapped. However, this only happens if there is no conflicting swap for either cell.
• The knight's move positions for a diagonal pair of cells are the cells that can be reached from both cells in the pair by moving two in one axis and one in another. A picture helps:

                      X - - -                 - - - X
                      - - * -                 - * - -
                      - * - -                 - - * -
                      - - - X                 X - - -
                  

  The X's are the knight's move positions for the pairs of cells represented by asterisks.
• In this bounded implementation, swaps are not allowed with cells outside the boundary.

Note that since only swaps are allowed, the number of 1's and 0's is fixed for any set of initial conditions. One may think of the BBX CA as a set of rules for moving 1's around on the lattice.