Reversible Cellular Automata
An Introduction
To be of much practical use, computational models must eventually
be constructed in hardware.
In order to co-operate with nature - rather than fight against
her - there are a number of laws of physics which computational
models should attempt to reflect as closely as possible.
- Locality
- Physics is chiefly characterised by local interactions.
There appears to be a fundamental limitation on the speed of information transfer
between spatially separated points.
EPR experiments are sometimes cited as indicating quantum events characterised as being
fundamentally non-local. However, as this non-locality may not be utilised for the transmission
of information, the effect may be ignored in this context.
- Locality implies that miniaturization increases speed. Normally,
the smaller your computational elements are, the more of them can be
packed together in any given volume, and the faster the resulting computer.
- Reversibility
- The laws of physics appear
to be completely microscopically reversible. In fact, as far as we
can tell, the laws of motion also appear to be time-reversal invariant under
the operation of simultaneously reversing the momenta of all particles - and
replacing every particle with its anti-particle.
- Reversibility implies that information can be neither created nor
destroyed, and that a variant of the second law of thermodynamics is likely to
be applicable to the system.
The locality property immediately suggests the use of
cellular automata as a model of the foundations of computational
mechanisms.
The significance of reversibility may be less clear.
reversibility is covered in a separate essay.
Some more details relating to future cellular automata hardware
may be found here.
As locality and reversibility are both of primary importance it
seems desirable to use reversible cellular automata as a basis
when developing discrete, finite models of physics or
computation.
|