> See http://www.escribe.com/science/theory/m2793.html for a universal
> dovetailer written in LISP. Among the LISP programs you have all the
> simulation of Fortran programs, Joel's minimal cellular automata,
Yes, this is true. But (of course :) I would like to argue in favor of
cellular automata over Turing Machines and even the Universal Dovetailer.
Somehow, though I can't fully express the idea in my head, they seem more
"natural" to me... and perhaps more "obvious" to other sentient entities.
Some of my reasons are as follows...
Turing Machines usually require many internal states, while CA need only
two. TMs also contain a *moving* part - the read/write head, and it's not
exactly clear how to implement such a gizmo outside of physics, or justify
such complexity when simpler machines exist. (Depending on your idea of
simplicity of course!)
You could imagine, for example, a cellular automaton that could run a Turing
Machine with a real read-write head that moved and everything - but with no
moving parts. Yes, I know these things are all equivalent, but to me, CA
require fewer assumptions or explanations.
Furthermore, Turing Machines tend to slow down as the size of the universe
grows larger, while cellular automata may be made arbitrarily fast, once the
synchronization problem is addressed. (Plamen showed me how this is not too
difficult to do actually.)
Finally, CA require no (3rd person) interpretation as to the special
relationships between bit patterns. They are represented naturally in the
geometric cellular space.
All of this may seem academic really, since we all know that any universal
computer is as good as any other. It's kindof like arguing about the kind
of wood God's stool is made out of! But there MAY be some reasons to want
to know exactly which algorithm is really being run on the bottom...
Because all of these implementations have slight differences as to the core
informational process they represent. Yes, they all do the same thing in
the long run, but the order in which they do things may be different. And
if we are anywhere near the "bottom" of it all, then we may be able to take
advantage of knowing that order.
For example, suppose we run my cellular automaton and find certain core
particle interactions that are extremely common. We might then recognize
these in a laboratory and better understand conventional physics.
Ok, that's a really weak argument, since I also believe that this world is
made up and that its physics is rather arbitrary.
But.... if it IS made up, and we are SUPPOSED to figure out the workings of
the automaton, then MAYBE ... the simulation would be made to resemble the
workings of the machine down below.
Ok, I'm rambling. I'll stop.