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


  • 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

This article a copy my answer posted in response to a quora question :  Is DNA a Turing machine?