The Margolus neighbourhood

One of the simplest partitioning schemes is the Margolus neighbourhood, named after Norman Margolus and studied extensively in a book he co-authored, Cellular Automata Machines (CAM).

This consists of dividing a grid of cells into into groups of four, to which the automata's rule is applied completely locally.

If exactly the same partitioning scheme were to be used repeatedly, then information would be unable to propagate beyond the confines of any individual partition - and the dynamics of the overall system would be sterile.

The partitioning scheme is thus applied using grids that occupy different spatial co-ordinates on alternate time steps. Hopefully the following diagrams will illustrate how this works:

Margolus neighbourhood

(t & 1) = 0

(t & 1) = 1
(t & 1) = 0   (t & 1) = 1

Alternation

As prominent examples of reversible cellular automata using the Margolus neighbourhood, CAM demonstrated amongst other things:

  • an implemetation of the HPP (Hardy, Pazzis, Pomeau) lattice gas, which exhibits circular wave propagation and approximately obeys the Navier-Stokes equations;
  • a model of diffusion processes, using a stochastic rule;
  • a model capable of universal computation, inspired by Edward Fredkin's billiard-ball model.
Use of the Margolus neighbourhood can have a slight disadvantage: in order to implement it in hardware, in addition to the state of each cell additional information is required to determine how each cell is updated - in the form of information about which partitioning grid is currently in use. This is not needed with (for example) the Star-Of-David neighbourhood.

The Margolus neighbourhood generalises neatly three dimensions. The result is the Necker neighbourhood.

Tim Tyler | tim@tt1.org | http://cell-auto.com/