</COMMENT> <h4>Unfortunately, your browser does not support Java.<BR> A Java applet is the central focus of this page.<BR> You're encouraged to try again using a Java-aware browser.</h4>
A version of this applet using the native VM is available here


This applet displays a cellular automata designed to illustrate a variety of types of reversible diffusion.

It uses a a number of different "partitioning neighbourhoods" to do this.

In particular the Q*Bert neighbourhood, the Star of David neighbourhood and the Margolus neighbourhood are the partitioning schemes used to help construct the reversible automata.

Various classical Margolus automata are also demonstrated, perhaps most notable the original Margolus neighbourhood implementation of Fredkin's Billard Ball Machine (BBM).

All the automata here are completely reversible. It is interesting to allow the automata to evolve for a period, and then click on the "Reverse" tickbox, to observe that the initial state is indeed recovered.

Th applet demonstrates both uniform and non-uniform cellular automata. The non-uniform automata are called things like "Lichen", "Ultra noise" and "Non-uniform gas".

Reversible automata have applications in simulating gasses and liquids, and associated physical phenomena.

They are important in modelling the physical foundation of computation.

Non-uniform reversible automata have applications in cryptography:

  • They may be used for generating streams of random numbers, without allowing any entropy present in the initial seed to leak away as the automata evolves;
  • They are also important for designing symmetric cypher systems. As a simple example of the technique:

    The rules of the automata are set with by the key, using certain types of "maximally non-linear boolean functions". The automata's initial configuration is set to the plaintext. More than enough iterations are applied so that influences have time to propagate across the entire automata. The resulting configuration is the cyphertext. Decrypting uses the reverse proceedure via the automata's inverse to recover the plaintext.

Interactive controls

  • Type - controls what rules the automata uses:
    • Margolus
      • Non-uniform gas: gas diffusion using a non-uniform automata
      • Bounce gas I: a uniform "gas";
      • Bounce gas II: another uniform "gas";
      • Lichen I: diamond-shaped wave fronts and rapid growth - a non-uniform automata
      • Lichen II: more rapid growth - a non-uniform automata
      • Ultra noise: Information diffusion - using a non-uniform automata
      • String thing: String shaped patterns
      • String thing II: More string shaped patterns
      • Rotations I: Limited diffusion;
      • Rotations II: Limited diffusion;
      • Rotations III: Slow, random-looking diffusion;
      • BBM: implementation of Fredkin's Billard Ball Machine - from Cellular Automata Machines;
      • HPP-GAS: Hardy/Pazzis/Pomeau lattice gas - as described in Cellular Automata Machines;
      • CRITTERS: "Gliders" - as described in Cellular Automata Machines;
      • TRON: A "trip-a-tron" - from the pages of Cellular Automata Machines;
      • SWAP-ON-DIAG: A gas with no particle interactions - as described in Cellular Automata Machines;
    • Triumphant, Q*Bert and Star of David
      • Non-uniform Gas: a "gas" with particle conservation;
      • Lichen I: diamond-shaped wave fronts and rapid growth - a non-uniform automata
      • Lichen II: more rapid growth - a non-uniform automata
      • Gaseous: a uniform "gas";
      • Universal computation: the closest thing to the BBM;
  • Use - tool selection - controls which type of tool to use to manipulate the environment;
  • Click to - set the tool's behavior - controls how the tool in use is applied;
  • Display - controls which aspect of the automata is presented;
  • Size - controls how many cells are displayed, and their size;
  • Show frames - configures how frequently the display is updated;
  • Delay - configures how much delay occurs between frame updates;
  • Noise level - allows the level of noise present to be controlled;
  • Neighbourhood - choose between the Q*Bert, Star of David and Margolus neighbourhoods;
  • Step - allows a paused automata to be single-stepped;
  • Reverse - simply toggle this checkbox to reverse the action of the automaton;
  • Pause - allows the automata to be stopped and started;
This applet can also be run as an application. Download this jar file (using shift-click) and double-click on it.

Index | Links

Tim Tyler | Contact http://hex.alife.co.uk/