Crystalline ComputationCellular automata 'in-silico'Crystals appear to offer a number of obviously attractive features to those in search of physical implementations of cellular automata. They are engineered by a process of self-assembly on atomic scales into regular patterns which mirror the lattices used in many automata.Local interactions between particles on the surfaces or within crystalline material or clays may offer an attractive way of implementing cellular automata on very small scales. Ideally, what is most urgently required is a way of implementing an automata capable of universal computation on very small scales. This page takes a brief look at some of the difficulties which will be involved in the process of creating such a physical object. Simple-minded approaches failFirstly one approach to implementing an automata such as the billiard ball model on a small scale involves finding a physical system which implements it using direct physical equivalents of billiard balls and mirrors.If a surface could be found, upon which an array of mirrors could be etched, and then the atomic-scale equivalent of billiard balls projected into the machine, then the system would be capable of universal computation. Approaches along these lines all appear fundamentally flawed. Uncertainties in the position and momenta of the 'billiard balls' will lead to ever-increasing errors in computation as the evolution of the system unfolds. While it seems attractive to represent the billiard balls by real partiles with real momenta, it is not easy to see how such an approach could succeed in practice. Attempts to eliminate cumulative errors by essentially changing this analogue system into a digital one appear to be necessary.
Digital synchronyIn a digital system, discreteness of time means that automata usually need to have a method of keeping their separate parts synchronised.It would be nice if we could independently clock our components using extremely accurate atomic-scale clocks - such as those found in the crystals which maintain synchrony in modern computers. Unfortunately, this hope appears to be a little optomistic. While it is possible to build reliable automata out of stochastic components with no synchrony between them, following the KISS rule (Keep It Synchronous, Stupid) it seems to make some sense to try to build a synchronous automata. This means that a component of any small-scale automata will need a clock. For systems above a critical size threshold, it will not be possible to source the clock frequency from a single source, due to problems involving the propagation delays which occur when the clock signal needs to trvel more than a short distance. Instead one proposed solution is to use a firefly system. This uses local interactions to maintain global synchronous behaviour. That it is possible to build such a discrete system with unreliable components which nevertheless exhibits global synchronous oscillations is illustrated in nature by fireflies. Thousands of such creatures may come to flash on and off in unison with one another, despite the perceptions of individual fireflys being dominated by their neighbours' lights. Very rapid 'firefly' devices have been implemented which illustrate that the process scales to high speeds reasonably well. Whether it is more cost effective to employ a propagated clock-signal at small scales and try to produce larger-scale synchronisation using firefly techniques is a question beyond our scope here - however it seems certain that if large synchronous systems are to be constructed, messaging techniques employing firefly-like local communication to attain global synchronisation will be required.
A thought experimentAs interactions on small scales will probably be primarily mechanical in nature it is instructive to imagine how one would build an automata which implements a billard ball machine using macroscopic components, such as ball bearings, rods, levers, etc.For this thought experiment it is probably best to ignore the force of gravity, as this does not scale well to small scales. A source of synchronous clocking signals may be assumed, initially. Ideally, the model should need as little power as possible to run. If you perform this experiment yourself you will probably find that although the billiard ball machine is not very complex, it's not easy to visualise a mechanical physical system which implements it.
ConstructionIt seems unlikely that a simple physical model of an automata which exhibits the property of universal computation will be found naturally.On the assumption that efficient, cheap nano-scale construction capabilities will not soon be realised it is worth considering some alternatives which may be able to offer a basis for the synthesis of matter capable of universal computation. Foremost among these is the possibility that organisms could be used to manufacture such entities at very small scales. It seems plausible, that if it were possible to apply suitable selection pressures, it would be possible to breed microorganisms to build a protein machine with the desired characteristics, or construct such a machine from inorganic materials. On this front there has been some progress, notably boolean logic gates have been 'manufactured' inside existing cells. See the [cellular logic gate] pages at MIT for further details. If it not currently clear which type of approach would have most chance of meeting with success in this area. Norman Margolus appears to be one of the few modern propoenets of crystal computation. He has written a [recent document] relating to it. HP have also worked on crystal computation. There are a number of links to their work on our [nanotechnology links page.
|