Bruno: > 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, > etc.
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. Joel
