Wednesday, October 24, 2007

Simplest universal Turing machine discovered

Turing is perhaps the grandfather of modern computing. In 1936-1937 he imagined a machine which could read binary (1,0) on a single tape either on the left or the right of the tape with a moving head and was capable of changing the state of each bit of information. It was known as a turing machine. In 1947 he said: "It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine.". Essentially a computer capable of performing any function can be constructed, the question is how simple can you make it....

Well Stephen Wolfram, author of the crazy book, "a new kind of science", offered $25K to anyone who could prove that a machine with 2 "states" and 3 "colours" is the simplest universal turing machine. Well Alex Smith, an undergrad from the UK just won the prize. What does this mean to biology? Well here is Wolfram's take on it...

"Early definitions of universality assumed that programs for a Turing machine must involve only a finite number of "nonzero bits"--and that the Turing machine must "halt".

But the 2,3 Turing machine--like modern computers (or systems in nature)--doesn't "halt". And in Alex Smith's construction the Turing machine "tape" (i.e., memory) must be filled with an infinite pattern of bits. [...]

Perhaps one day there'll even be practical molecular computers built from this very 2,3 Turing machine.

With tapes a bit like RNA strands, and heads moving up and down like ribosomes.

When we think of nanoscale computers, we usually imagine carefully engineering them to mimic the architecture of the computers we know today.

But one of the lessons of NKS--brought home again by Alex Smith's proof--is that there's a completely different way to operate.

We don't have to carefully build things up with engineering. We can just go out and search in the computational universe, and find things like universal computers--that are simple enough that we can imagine making them out of molecules."

I'm not too sure what it means, but it sounds cool. Perhaps life is already "designed" like a universal turing machine, running software on cells which all date back to a comon ancestor turing machine and linked through a series of unbroken cellular divisions as Kim Nasmyth so eloquently pointed out...


Bayman said...

I had searched the computational universe for the simplest possible universal Turing machine.

Where is this computational universe and how big is it? Sounds like a pretty vast search space...Did he really "search" it, or did he just pick the smallest possible number of states and colors??