Anand CV Mallaya

Archive for February, 2015|Monthly archive page

Is DNA a Turing machine?

In Uncategorized on February 8, 2015 at 12:57 pm

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 <=> Proteins

Formal 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

  1. The head only moves in one direction.
  2. The output tape is different from the input tape

Is DNA a Turing machine?