Introduction
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.