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.

Tim Tyler | Contact |