Friday, June 13, 2003

More on Turing Completeness

Here's the thing that gets me. Proving something Turing complete is saying that it's at least as powerful as the Turing Machine. So let's say that all of our computers were finite automata, and then we discovered a Turing Machine in a ditch somewhere. It's like we ran an automaton program on it, proved it was "automata complete," and then never worried about all those pesky tapes and reading and writing.

Absurd, right? But that's exactly what we've done with DNA. DNA is an amazing thing. It "executes" (obviously this is a flawed metaphor) every base in parallel, simultaneously activating and inhibiting other stretches of the gene. Does that sound like a Turing Machine? It most certainly does not! But because some fairly bright people figured out how to simulate a TM with DNA, the story seems to have ended.

By the way, I've revised yesterday's entry slightly because on rereading it I noticed that it wasn't particularly clear on a couple of points. Absorbtion blog in action.