Reversible Cellular Automata

An Introduction

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

Reversibility, however may need some further elucidation.

Models of computation which are not microscopically reversible, typically lose information in the process of execution. As the laws of physics appear to be reversible, that information cannot really be being lost, it must be being translated into another form. That form is usually heat.

If energy is continuously being dissipated in the form of heat, then a power supply will also be needed to replace that which is being lost.

Estimates concerning the relative importance of heat dissipation due to irreversibility in todays microprocessors estimate that this energy will become important by around 2010 and will become a primary limiting factor by around 2020.

This estimate is based on Moore's law - which appears to have held at least in part due to the fact that recent improvements in computing speed have occurred by progressively minaturising electronic transistors.

There are a number of reasons to believe there will be significant hiccups in the rate of increase in speed of computers before 2010 - these reasons may be briefly described as being due to nanotechnology and quantum computation.

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 models of physics or computation.