Answer by Anand Mallaya:
DNA may not be a Turing machine, but it can,very much likely, be part of a Turing Machine.
A Turing machine consists of
1. A Tape – A tape divided in to cells. Each cell capable of holding a symbol from a finite set of alphabets.
2. A Head – Which can move left or right through the tape and read the alphabets in the tape.
3. A State Register – A register which stores the state of the machine.
4. An Instruction Table – Which based on the state of the machine and the alphabet on the cell in which the head is currently reading, performs one of the set of predetermined actions.
Examples of instructions can be like
Write an alphabet on the cell
move the head right or left
stay on the same cell etc.If you compare this with a biological cell, we can find many interesting features of the cell which can be related to a turing machine.
Tape <=> DNA
Head <=> Ribosome
State Register <=> RNA
States <=> Amino acid
Instruction Table <=> DNA codon table
Ouput Tape <=> ProteinsFormal Definition of Turing Machine
A (one-tape) Turing machine can be formally defined as a 7-tuple
where
is a finite, non-empty set of states
is a finite, non-empty set of tape alphabet symbols
is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
is the set of input symbols
is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)
is the initial state
is the set of final or accepting states.
The Function
The function being performed is finite time and is the Protein biosynthesis
The Instruction Set
Notable differences are
- The head only moves in one direction.
- The output tape is different from the input tape