Citation: Gács, Peter. "Reliable cellular automata with self-organization." Journal of Statistical Physics 103 (2001): 45-267.
Web: https://arxiv.org/abs/math/0003117
Tags: Computer-scientific, Universal-scheme
This visionary paper shows how to make a universal fault-tolerant cellular automaton in one dimension.
The idea of making a universal fault-tolerant cellular automaton is obviously very interesting. If there were no way to do this, then that would mean that noise will always necessarily corrupt our ability to compute, which we expect to not be the case. The results from this paper can be used to make a reliable one-tape Turing machine which can perform arbitrarily large computations under fixed but small noise:
> Çapuni, Ilir, and Peter Gács. "A reliable Turing machine." arXiv preprint arXiv:2112.02152 (2021).
The question of fault tolerance in cellular automata has been one of the focuses of the theory of cellular automata since their original invention by von Neumann:
> Von Neumann, John. "Probabilistic logics and the synthesis of reliable organisms from unreliable components." Automata studies 34.34 (1956): 43-98.
From the condensed matter physics perspective, it is obvious that the result of Gacs corresponds to some strange 1-dimensional phase of matter which breaks all previous classifications. This is made all the more mysterious by the large length of the paper (230 pages), and the impressive size of the sites on the one-dimensional lattice.
Many people in quantum information and quantum phases see the work of Gacs as an inspiration, because if it can be translated to the quantum setting it would break our conjectured classifications of topological phases.