Universal Turing Machine can be boiled down to two components. Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending on input provided by the tape.

From this point of view cells have some properties very similar to UTMs, the DNA is in an essence a tape of instructions that can be read and written to. Rest of the cell behaves similar to action table, defining rules that guide which part of DNA is read and when it happens, a moving "head" along DNA "tape".

Subquestion 1: DNA can be used for computation. Can entire cell be used for similar purposes?

Subquestion 2: If every living organism contains at least one UTM is it possible that all organism are in some sense Turing Complete?

  • 2
    $\begingroup$ In vivo DNA has some physical/biological bounds on its own length, making the "tape" a bounded one. It's hard to claim that is a TM. (By the same coin, a laptop is not Turing-powerful, either.) If instead we consider an "ideal" DNA model, where DNA can be arbitrarily long, we can reach Turing-completeness. $\endgroup$
    – chi
    Apr 4, 2016 at 12:47

3 Answers 3


Every living organism has -- to our knowledge -- only a finite amount of resources available. So no, they can not be Turing-complete.

That said, there is quite a number of bio-inspired models of computation that can be studied formally. Sticker systems [1], for instance -- an abstraction of recombining DNA fragments -- can be shown to reach Turing-power when we assume infinite resources. Splicing systems [2] are another example.

I am not aware of any abstractions of entire cells. To my knowledge, we do not have a full understanding of how cells work so that is out of reach -- today.

Note: Turing-completeness requires programmability resp. universality. Can you elicit any response from a cell by applying suitable stimuli? I wouldn't think so. In my opinion, any given cell is more likely to correspond to a specific program with a specific purpose.

  1. Sticker Systems by G. Păun and G. Rozenberg (1998).
  2. Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors by T. Head (1987).

Turing machines do not have infinite but unbounded tapes. In his paper, Turing describes his machines as a model of human computers. (The word "computer" at the time mainly referred to the young people employed to process the UK census data :) He was very careful about his infinities, and he specifically said that the tape was unbounded. A human computer could always use more notebooks, and a Turing machine could always add more tape so that the head never falls off. But it always has a finite history. Your laptop can always buy more memory, but it never needs infinite memory. The essence of Turing's computer is that there is a universal evaluator of all programs, including the programs for the universal evaluator. The ribosomes transcribe genetic code which regulates among other things cell division, which leads to more cells with more ribosomes. But there are, of course, many different computers, and many different kinds of cells, and not-quite cells, which compute in many different ways.


There are many bio-inspired models of computation. As Raphael has already stated, real implementations would always have the limitation of finite resources. This aside, Membrane Computing uses abstractions of cells with their compartments as the computing hardware. However, they use the quantities of different objects/molecules in the different compartments as memory, not DNA.

The DNA-based models like the sticker systems mentioned by Raphael or also splicing systems do not care about the rest of the cell, but only take DNA as a memory and some enzyme's action on it as the computing operation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.