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?
Asked By : user1561358
Answered By : Raphael
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.
- Sticker Systems by G. Păun and G. Rozenberg (1998).
- Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors by T. Head (1987).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/55426
0 comments:
Post a Comment
Let us know your responses and feedback