Fault-tolerant cellular automata
My fault-tolerant cellular construction has appeared in the work
B.S. Cirel'son, "Reliable storage of information in a system of unreliable components with local interactions." Lect. Notes Math. 653 (1978), 15-30 (transl. from Russian 1977). [MR58#20899]
P. Gacs, "Reliable computatiion with cellular automata." J. Comput. System Sci. 32:1, 15-78 (1986). [MR88d:68081]
P. Gacs, J. Reif, "A simple three-dimensional real-time reliable cellular array." J. Comput. System Sci. 36:2, 125-147 (1988). [MR89m:68102]
In 1953, von Neumann proposed a design for reliable Boolean circuits.
Cellular media are desirable computing devices [...] In 1974, solving a problem arising in mathematical physics, Toom constructed some two-dimensional infinite cellular spaces capable of holding a bit of information for any number of steps. In 1976, Tsirel'son constructed a one-dimensional medium holding a bit in n cells for a nearly exponential number of steps. However, Tsirel'son used components of three different kinds, and the kind of the component changes in both space and time according to a grand plan not subject to errors.
In , using some of Kurdyumov's ideas, Gacs constructed a one-dimensional cellular space M capable of reliable computation.
(Gacs and Reif, p. 126.)
The grand construction of Gacs implements a number of ingenious ideas of himself and his precursor Kurdyumov, but one idea is due to me:
[...] the simple task of protecting a bit of information requires the capability of carrying information to large distances reliably. It is hard to imagine how to do this without setting up some structure, "division of labor" among cells: assigning roles to cells in a way varying in space and time. Tsirel'son did this [...]
(Gacs, p. 18.)
By the way, fault-tolerant quantum computation also assigns roles to cells in a way varying in space and time according to a grand plan not subject to errors (using a classical control unit). Of course, the quantum construction is much more complicated than my classical construction, and involves a number of new ideas.
* * * * * * * * * * * * * * 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 1980 1990 2000
Adamatskiy, Aharonov, Ben-Or, Gacs, Gray, Kurdyumov, Levin, Rajagopalan, Reif, Schulman, Toom. (Detail)
|back to my homepage|