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.