The hypothesis that the number of possible states of every finite volume of space-time is finite.



One familiar feature of the natural world is that it contains particles that can move with a range of speeds, in a range of directions.

It seems desirable to be able to model this sort of behavour in cellular automata - perhaps using structures similar to gliders.

There are several approaches to doing this. These can be broadly categorised according to whether they represent speed and velocity in the state of individual cells, or in the form of spatial configurations. Either approach is possible, as well as hybrid approaches that combine elements from both.

I refer to the choice between these two approaches as the "shape/state" dilemma.

The "state" approach generally uses big complex cells and lacks elegance. However, the "shape" approach seems more challenging to build decent models with since simple models rarely exhibit anything remotely approaching the desirable behaviour. Here we will be examining the "shape" horn of the dilemma - and will be looking at an automata with relatively simple cells - where both speed and velocity are encoded almost entirely as spatial configurations.


Our approach involves constructing a reversible automaton that supports worm-like motion.

The worms move using what can be described as "caterpillar track" motion. This contrasts with Fredkin's proposed "Earthworm motion" - as described on his motion page

The automaton is rather similar to our "revoworms" automaton.

The bottom surface of the worm rests on the ground. The top surface travels forwards towards the head of the worm. As it moves the upper surface rolls down onto the ground at the front of the worm, and the bottom surface at the end of the worm lifts up.

The head of the worm can move forwards or turn one way or the other. Instructions about what to do are transmitted around a cyclic loop, running along the top of the worm, acting in the head cell, and then resting on the ground before being picked up at the tail.

There are essentially four aifferent sorts of state - <empty>, <straight on> or <turn left> and <turn right>. The <empty> state is used to represent empty space - anything else represnets part of a worm segment.

The automaton uses the Doubled Central Triumphant neighbourhood.

This is effectively the same as the Central Triumphant neighbourhood with different maps applied on alternate time steps.

There are 2^12 (4096) states per cell. This is divided up into 4 states for each of the edge sub-cells, and 64 states in the central region.


The automaton exhibits "omni-directional gliders" - gliders can move in practically any direction.

More precisely, if a direction is specified, a glider and be easily constructed that travels arbitrarily close to that direction.

Variable speed gliders are also possible. In particular, for any possible specified direction an infinite number of different speed gliders can be constructed that move in that direction. The speeds have the property that - provided you do not approach the speed of light too closely they roughly approximate a continuum.

Some diagrams should help indicate how these properties have been achieved.

Direction as shape

This diagram shows how direction is effectively encoded as a vector. If there's a vector in the space with integer coefficients in some direction, a worm can be constructed that moves along that vector.

Speed as shape

Speed can be modified by the use of delay elements - and the delay can be varied linearly in an unbounded fashion. Provided you do not approach the speed of light too closely, fine graduations in speed are possible.


The automaton has been implemented as a Java applet. You can find it here.


I hope this automaton helps visualse one way in which simple automata can exhibit particles that can move in an unbounded number of directions at an unbounded number of speeds.

If anyone thought that a the finite nature hypothesis implied that only a finite number of particle speeds or directions need be possible, this model demonstrates otherwise.

I hope this model throws light on some of the the capabilities and limitations of the "shape"-based approach.

Future directions

Plenty of challenges remain.

For example, the model described here does not demonstrate anything remotely resembling Newtoniam mechanics when particles collide - there is no conservation of momentum.

Also, slow particles naturally tend to demand more material than faster ones. In the author's opinion, this is likely to be a common feature of many digital models - and explaining why faster particles tend to have higher energies, and break down into a number of slower ones is likely to prove to be a problem. It is a problem that could be solved by "padding out" the faster particles - but that does not feel like a neat solution.

In nature, it appears that some particles exist that can travel in any direction, but are never seen moving slowly. That seems like behaviour it would be challenging to reproduce using fine-grained "shape" models - though it seems easier to visualise how to model it in a "state"-based model.

Tim Tyler | |