Billiard ball machine

The billiard ball machine is a model that roughly simulates the action of "billiard balls" colliding with obstacles (#) and each other (0) on a two-dimensional playing field. Though different versions of the billiard ball machine probably exist, they all work about the same way. If some way of indicating direction of the balls (NE, SE, SW, NW) is added, the BBM essentially becomes a programming language. It then becomes Turing-complete if an infinite number of balls/obstacles is allowed.

Basic dynamics

Three types of collision are possible in this version:

0   0  0    0  0   0
 \ /    \  /    \ / 
 / \     ><      v  
0   0   /  \     #  
       0    0       

Any other type of collision gives undefined behavior. In case multiple collisions happen close by, the exact behavior of the billiard balls here is "handle all collisions, move half a step, repeat". Handling collisions is done by checking if there is a collision--two balls about to move into each other, or a ball about to move into a wall--and if so, changing the appropriate direction component(s) appropriately. (This also gives a decent way of handling the undefined collisions; making the billiard balls square is another option which may or may not give the same results.)

Logic gates

Logical gates can be constructed out of billiard balls and obstacles. The simplest gate is the "collision gate", and all other logic gates are essentially built from this one:

1     2
 \   / 
  \ /  
  /X\  
 // \\ 
AB   CD

This gate contains no obstacles (slashes and X mark all the possible paths); it simply works based on the presence or absence of billiard balls going in the right direction at positions 1 and 2. If there is a single billiard ball at position 1, in three steps it will be at position C. If a single ball is at position 2, it will go to position B. If there are balls at both 1 and 2, they will go to positions A and D. Therefore, A and D work as AND gates and B and C work as AND NOT gates.

Another important gate is the Feynman gate:

   1   2   
    \ /    
    /X>#   
   ///\    
  ///  \   
#<//    \  
 / \     \ 
A   B     C

A ball will come out position A iff one went in position 2. If a ball went into 1 but not 2, one will come out of C; if a ball went into both, one will come out of B. The important thing about this gate is that the presence or absense of a ball going into 1 has nothing to do with the apparent path of the ball that goes into position 2 (actually, if 1 is present, then 1 is what comes out of A, but that doesn't matter since all the balls are identical) even though the presence or absence of a ball going into position 2 does have an effect on the apparent path of the ball going into position 1.

Since the billiard ball machine is reversible, a gate can be presented with valid output in the correct places (e.g. balls entering the Feynman gate from positions A and B) and the corresponding input will come out; however, if an invalid output is supplied to the gate (e.g. balls going into all three outputs), behavior depends on the layout of the gate and, in some cases, the implementation of the BBM.

In bra-ket notation, these gates can be expressed as follows:

Collision: |0000><00| + |0100><01| + |0010><10| + |1001><11|
Feynman: |000><00| + |100><01| + |001><10| + |110><11|

Extensions

One simple extension is a duplication gate, which would duplicate (and, in reverse, un-duplicate) any incoming balls:

|00><0| + |11><1|

Another is the deletion gate, which could be used to throw away data (and break reversibility):

|0><0| + |0><1|

Since most of the billiard ball machine is reversible, an obvious addition is a modification of the Hadamard gate, a quantum gate, to conserve the number of balls:

(|01><01| + |10><01| + |01><10| - |10><10|)/sqrt(2) + |00><00| + |11><11|

The only thing required to make this a universal quantum computer now is at least one (quantum) phase shift gate whose angle in full circles is irrational. That angle is n in the following:

Phase shift: |0><0| + |1><1|*e^(2i*pi*n)

External resources

• Wikipedia:Billiard-ball computer may be relevant.
• A cellular automaton approximating a billiard ball computer.