self-replicating Turing Machines in OB
Tim Hutton
A few years ago now, Siamak pointed out that it was possible to make a
Turing machine in OB.
http://groups.google.com/group/organicbuilder/browse_thread/thread/79fb5f99434e6949
I didn't really make much of it at the time but recently Calcyman
wrote to me, pointing out that with a suitable Turing machine program
we could make self-replicating molecules. Together we made the
attached proof of concept. Go to challenge 3 ("line") and add the
reactions from the text file. First it hand-builds a molecule with an
encoding of the states 2-3-3-2-3 (just as an example) and then then
molecule proceeds to replicate itself (just the states, not the atom
types) through the operation of the Turing machine. The screenshot
shows a few copies a bit later. (I've increased the size of the world
and the number of atoms, from the default.) The python script explains
the state encoding and the operation of the Turing machine.
The replication scheme is much like Dave Mann's solution to level 15,
as mentioned in the OB paper: send messages up and down the molecule
specifying which atom to attach next. Only in this case the program is
specified as a Turing machine program and the traveling message is the
traveling read-write head. Calcyman's idea is that if the system
reactions coded for a *universal* Turing machine then the molecules
could in theory both control their own replication and evolve to
perform other actions as might be beneficial to them. We've a long way
to go yet, though, and I'm not even sure it's feasible. As I say the
attached is just a proof of concept. But it's an intriguing thought
and we would welcome your input.
I'm sure I haven't explained this very well so please ask me to
clarify anything. You can work through the Turing machine program from
the script on paper and it will make more sense. Start with
...00002332310000.. on the tape, and with the read-write head in state
GRAB ("A") positioned on the first 2. The notation of each quintuple
(e.g. "2,A,P4,R,B") is as here:
http://en.wikipedia.org/wiki/Busy_Beaver#Examples_of_busy_beaver_Turing_machines
So the first action is to print 4, move right, and adopt state B ( =
W0 = "Write 0").
Tim
--
Tim Hutton - http://www.sq3.org.uk
Take the Organic Builder challenge -
http://www.sq3.org.uk/Evolution/Squirm3/OrganicBuilder/
