Saturday, April 28, 2007

DNA as String Rewrite System

I'm currently reading Eric Baum's What is Thought. It presents an interesting comparison between the operation of DNA and Post production systems. These systems provide a set of regular expressions paired with corresponding substitutions. An example is the rewrite rule:

x B A B y -> x C B y

where x and y are variables.

When provided the string


the result of the substitution is

A C B C B C. (example from Baum)

These types of operations happen both at the levels of intron removal and protein synthesis. The more common (and easier to visualize) comparison is of DNA to a Turing Machine. Here the DNA (actually RNA) strand is the tape and the Ribosome is the read/write head.

Looking back, both comparisons were explored in Hofstadter's Godel, Escher, Bach: an Eternal Golden Braid and Metamagical Themas

UPDATE: In a later chapter Baum points out the Turing equalence (proven by Minsky, discussed by Wolfram and others) between Turing machines and Post production systems.

No comments: