George Johnson

A Shortcut Through Time
The Path to the Quantum Computer
New York 2003

Turing Machines and Cellular Automata

The classical Turing machine reads a cell, refers to its rulebook, and act accordingly: a 1 might be changed to a 0, already erased altogether, the read/write head then moving up or down the tape to the next estimated locale. That works fine with classical bits for but the Quantum Turing machine is processing Quantum bits. And the most basic truth of Quantum mechanics dictates that you cannot measure a qubit without destroying the superposition. The register that said 1 and 0 will randomly collapse into 1 or 0. The quantum juggling act will break down, the superposition bits falling to earth like so many dropped balls.

One way to get around the problem is to suppose that the read/write head itself is somewhat part of the quantum system. Confronted with a cell that says ¢, the head will also enter a superposition, registering both 1 and 0. As long as the information doesn't leave the quantum world there has been no measurement - the delicate superposition won't be upset. But this gets harder and harder to visualise since the head itself, being quantum-mechanical can't be restricted to any one place at a time. It would have to be in an even more convoluted superposition, reading all the cells at once. Pressed too hard, the metaphor crumbles.

Drawing another step closer to what the real quantum computer would be like requires shifting perspectives again, looking at computing in a subtly different light.

Take the image of the Turing machine, the cartoon version of classical computation (pg. 54 .....Computation is simply a matter of taking an input string and converting it, according to the rules of the programme, into an output string.), and dispense with the read/write head altogether, so all that is left is the tape.

The result is what mathematicians call a cellular automaton or CA - a deceptively simple device that can generate surprisingly intricate behaviour. Start the tape to the battle of cells coloured black (1) or white (0). Then each cell interact with its neighbours according to a strict menu of rules: "If the two cells to your left are black and the two to your right are white, then you must turn white also." Or "If the pattern to your left is white-black-white and all want to your right is black-black-white, then you must turn black." Any number of variations can be imposed. Once the device is set in motion, the cells interact with their neighbours and, at each tick of the clock, the pattern evolves kaleidoscopically, a scintillating pattern of black and white.

Watching a single row of cells blink rapidly on and off results in little more than dizziness. To make the pattern is easier to fathom, practitioners of this arcane art programme their computers so that each newly generated row is displaced beneath its progenitor. Pick the rules you want the system to follow, enter an initial sequence of cells and the pattern unfolds, taped by tick, strolling down the screen.(You can try this firsthand using the simulators available on several web sites.) Some configurations quickly get struck in a rut, settling into a dull repetitious cycle, stuttering ad infinitum.

Other automata churn out pleasingly symmetrical patterns.

And some produce gibberish.

But a few seem to evolve endlessly according to some secret plan, generating intricate designs - the tension between order and chaos we call "complexity".

Remember that computing can be thought of as taking a row of cells, the input, and converting it into an output: the pattern representing the answer to the problem. Thus, with a correctly crafted rules, the cellular automaton can be programmed to compute.

Suppose we want to make in adding machine. It would take as its input a row of cells coloured black or white, 1 or 0, that might look like this: 0000000000110111, for 2+3. Then it would France for itself into a pattern interpreted to mean 5: 000000000011111. (We not using the real binary here, just counting 1s) A different, more complex rule set might conceivably take a pattern representing some number and convert it, after many generations, into its prime factors, in the form of a sequence of black and white cells. The device would act, in other words, like a Turing machine but without the need for a read/write head.

Cellular Automata

HOME      BOE     SAL     TEXTE