4
$\begingroup$

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?

Improve this question
$\endgroup$
  • 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 '16 at 12:47
10
$\begingroup$

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).
Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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