Is there a theory of computation that takes failure and decay of the computation substrate into account?

Question

There are obvious differences between a Turing machine and a real computer. Not only is the latter finite in size, it is also prone to failures and it is made from decaying matter. The kind of framework I have in mind is this (but please excuse the handwavy vagueness): In some sense, (quasi)particles that constitute matter can be thought to perform computation: They have state that persists at least for some time (properties such as position, spin, charge, momentum) and they can change their state in feedback loops by interacting with other particles. The more elementary particles locally affect each other, the more complex the state and feedback loops can be. What kinds of computation we can perform on such a substrate depends on the configurations and rules that govern the particles, in particular, how many feedback loops they allow to simultaneously affect a local arrangement of particles. In this sense I'm looking for a framework that is analogous to the Chomsky hierarchy, i.e. in which the complexity of the system is successively extended to eventually build up to a notion of general computation. Is there something similar to this in the literature?

Answer 1

I'm not 100% sure what the question is about, but the title seems to ask about computation that allows failure. There is a lot of work on noisy (erroneous) computation in the sense that I think you are asking about. I don't have time to give a complete overview, but here are some pointers that may be of interest.

• Distributed systems. This is probably by far the most developed field because the very definition of a distributed system is based on the possibility of (partial) faults. There are elaborate theories of DS depending on the chosen fault model, e.g. fail/stop or byzantine failure. See also the work on failure detectors.

• Cryptography. This may seem a bit bizarre, but I think much of the field of cryptography can be seen as a form of extreme failure, with the adversary trying to undermine (in a general sense) the working of the system. You can think of the usual polynomially bound attacker as an case of failure model. This lead to things like secure multi-party computation as an algorithmic tool in the face of extreme adversity.

• π-calculus: see (1) for a generalisation of Shannon-style information theory to interacting processes. I think the error model in (1) is unrealistic, because it does not cater for the situation where an error converts a free into a bound name or vice versa.

• Turing machines: see (2, 3, 4).

• Cellular automata: various researchers have added failure models, sorry no references at the moment, maybe look at work by P. Gacs.

• λ-calculus: see (6).

• Assembly language: see (5, 7).

• Quantum computation: is all about error correction, I'm not qualified to say more on this.

• An increasingly important subfield of computation is the use of probabilistic process calculi to model chemical reactions. Have a look at Luca Cardelli's recent work.

Note also that this line of thinking is very old: J. von Neumann wrote about this in 1956 [8]. Maybe even more impressive C.-A. Petri invented Petri-nets in August 1939 at the age of 13 for the purpose of describing chemical processes.

---

1. M. Ying, Pi-Calculus With Noisy Channels.
2. I. Capuni, P. Gacs, A Turing Machine Resisting Isolated Bursts Of Faults.
3. I. Capuni, Fault-tolerant Turing Machine.
4. E. Asarin, P. Collins, Noisy Turing Machines.
5. J. Chang, G. A. Reis, D. I. August, Automatic Instruction-Level Software-Only Recovery.
6. D. Walker, L. Mackey, J. Ligatti, G. A. Reis, D. I. August, Static Typing for a Faulty Lambda Calculus.
7. F. Perry, L. Mackey, G. Reis, J. Ligatti, D. I. August, D. Walker, Fault-tolerant Typed Assembly Language.
8. J. von Neumann, Lectures on Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components.

Answer 2

Rabie introduced the model of "Rusted Turing Machines" in his thesis: The Power of Weaknesses:What can be computed with Populations, Protocols and Machines (Chapter 7).

The idea is that there is a restriction on the number of time the TM can change its internal state because of decay. Rabie introduced the class $Piv(f(n))$, the class of Turing Machines that change their internal state $O(f(n))$ times. An RTM is then an element of $Piv(1)$.

In this model, Rabie

• gave some results on different languages that can be computed;
• showed that he halting problem of RTM is decidable;
• provided upper bound for the busy beaver problem with RTM.

Answer 3

the question is challenging in its broadness & disclaimer of vagueness however some areas of research can be cited that impinge on it. roughly the 1st half of the question is about unreliable models of computation and the 2nd half is asking about a "hierarchy" built out of such unreliable systems.

a general trend in CS and computer engineering is that "noise is the enemy" and many auxiliary systems are built to reduce/ minimize/ suppress it, even with new models of computation eg quantum computing. the theme that "reliable systems can be built out of unreliable ones" via many techniques is a broad theme in CS & its related engineering. so a "hierarchy" does indeed exist in the sense that larger systems are built out of subsystems but the general idea is to remove noise/ error in the subsystems.

• spintronics (eg found in recent Nature articles) is a new general term and area of investigation given for harnessing sub-electronic effects such as electron spin for computation, and also encompasses quantum computation. electron spins are extremely delicate to manipulate, nearly an analog phenomenon, and subject to the Heisenberg uncertainty principle in measurement. by the way one of the leading systems for minimizing noise in QM computation cited by experts is the Martinis lab approaches, recently acquired by Google & published in Nature: State preservation by repetitive error detection in a superconducting quantum circuit, Kelly et al

• error correction in RAM has been used for many decades. it was discovered that some chip packaging was slightly radioactive and caused RAM to be unreliable by altering bits (aka, literally, as asked, "decay"). Hamming codes were used to correct this (in one of the early applications of them). some fraction of the RAM is dedicated to the error correction. this can be seen as a sort of hierarchy where the low-level RAM is unreliable but the overall system/ abstraction improves reliability to a high degree. the same technique is used in modern Flash memory. survey/ refs can be found in this paper: Error correction in Flash memory / Worley

• TCP/IP and many other network protocols are an example where noisy subsystems are "fixed" with error correction. packets have "checksums" and are rebroadcast if consistency errors are detected by the receiver. the so-called network protocol "stack" is also a hierarchy-like construction.