Random
</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.

Introduction

This applet displays a cellular automata designed to illustrate pseudo-random number generation using a cellular automata.

Pseudo-random number generatiors are frequently used in computer science - they're frequently important in security systems that employ cryptography.

For certain applications it makes sense to have very small and fast pseudo-random number generators which can be implemented directly in silicon. Cellular automata are probably the best models for this type of random number generator.

Automata that are used for generating random numbers should generally be reversible. Irreversible automata "leak" information - and a loss of information leads to cyclic behaviour, and predictability, rather than randomness.

We have written a paper which discusses issues relating to randomness and reversibility #in random number generation. It is available here.

With this in mind, our automata primarily employs a variant of the Margolus neighbourhood, the X neighbourhood. Using this type of neighbourghood it is easy to generate reversible automata automatically. The automata we use are mainly lattice gasses.

One potentially-useful property of lattice gasses in this context is that they can be made to obey the law of conservation of "matter". This allows the density of set bits in the random stream to be precisely controlled.

This applet demonstrates one non-uniform cellular automaton.

Non-uniform cellular automata appear to have great potential as random number generators.

Interactive controls

  • Type - controls what rules the automata uses:
    • Lattice Gas: a classical lattice gas
    • Bounce Gas: a "gas" with non-momentum-preserving collisions but more dynamic behaviour
    • Non uniform: mixture of the above types, with some "twist" cells thrown in
  • Tool selection - controls which type of tool to use to manipulate the environment;
  • Tool behavior - controls how the tool in use is applied;
  • Display - controls which aspect of the automata is presented;
  • Resolution - controls how many cells are displayed, and their size;
  • Wrap around - if on the automaton takes on the geometry of a torus;
  • Show frames - configures how frequently the display is updated;
  • Noise level - allows the level of noise present to be controlled;
  • Randomise - restarts the automata with the current initial configuration;
  • Clear - completely clears the grid;
  • Step - allows a paused automata to be single-stepped;
  • 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 | HAL | EoSex | Firefly | Random | CA | Links

tim@tt1.org | http://www.alife.co.uk/