blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html
The Simplest Universal Turing Machine Is Proved October 24, 2007 Stephen Wolfram "And although it will no doubt be very difficult to prove, it seems likely that this Turing machine will in the end turn out to be universal."
I had no idea how long it would take before the prize was won. Perhaps the question was even formally undecidable (say from the usual axioms of mathematics). But today I am thrilled to be able to announce that after only five months the prize is won--and we have answer: the Turing machine is in fact universal! Alex Smith--a 20-year-old undergraduate from Birmingham, UK--has produced a 40-page proof.
Principle of Computational Equivalence (PCE) that I introduced in A New Kind of Science. We are also at the end of a quest that has spanned more than half a century to find the very simplest universal Turing machine.
There were some simpler universal Turing machines constructed in the mid-1900s--the record being a 7-state, 4-color machine from 1962. That record stood for 40 years--until in 2002 I gave a 2,5 universal machine in A New Kind of Science. And from searching the 2,985,984 possible 2,3 machines, I found a candidate. From our everyday experience with computers, this seems pretty surprising. After all, we're used to computers whose CPUs have been carefully engineered, with millions of gates. It seems bizarre that we should be able to achieve universal computation with a machine as simple as the one above--that we can find just by doing a little searching in the space of possible machines. That in the computational universe, phenomena like universality are actually quite common--even among systems with very simple rules. It's just that in our normal efforts of engineering, we've been too constrained to see with such things. From all my investigation of the computational universe, I came up with the very general principle that I call the Principle of Computational Equivalence. What it says is essentially this: that when one sees behavior that isn't obviously simple, it'll essentially always correspond to a computation that's in a sense maximally sophisticated. One might think that computational ability would be a more gradual phenomenon: that as one increased the complexity of the rules for a system, the system would gradually show greater computational ability. It says that above a very low threshold, all systems will be exactly equivalent in their computational capabilities. And if that's true, it has some pretty fundamental consequences. But--like many fundamental principles in science--it's not the kind of thing one can abstractly prove. Instead, one has to figure out whether it's true by accumulating evidence--in effect, by doing experiments, and seeing how they come out. Well, one of the predictions of PCE is that as soon as one sees something like a Turing machine whose behavior is complex, the system will end up being universal--even if its underlying rules are really simple.
And as of today we know that the prediction of PCE also checks out there. But unlike some science experiments, it didn't take a multibillion-dollar particle accelerator. I really wondered what kind of person would win our prize. I gave it about even odds of being a "professional" or an "amateur". I didn't know if the proof would require fancy number theory or other mathematics, accessible only to a "professional". Or if it could be done purely in explicit "elementary" computational terms. But at 20:53:59 GMT on Saturday, June 30--just 47 days after we announced the prize--we received a submission, with the description of the submitter given as "Alex Smith is an undergraduate studying Electronic and Computer Engineering at the University of Birmingham, UK. He has a background in mathematics and esoteric programming languages." But it hadn't quite proved universality--because it still in effect required a separate universal computer to set up each program for the 2,3 machine. And six days later a revised proof arrived--that got much closer.
One of the members of the committee asked whether the proof really satisfied the formal definition of universality that he'd given in a seminal paper in 1956. And a few weeks later we received another version clarifying that point. 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" (ie, memory) must be filled with an infinite pattern of bits. But the key point is that the pattern of bits can be set up without doing universal computation. So that means that when we see universal computation, it's really being done by the 2,3 machine, not somehow by the encoding we're using. What Alex Smith needed to do to establish universality and win the prize was just to show that there's some way of programming the 2,3 machine to do any computation. That it's possible to make a "compiler" that compiles "code" for some known class of universal machines to code for the 2,3 machine. But his "compiler" doesn't make terribly compact or efficient code. In fact, for anything but the simplest cases, the code tends to be astronomically large and horrendously inefficient. The point is one of principle: the 2,3 Turing machine is universal. No doubt it'll be possible to find much better compilers, that make much better code. 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 telephoned Alex Smith a few days ago, to tell him that we were finally convinced that he'd solved the problem and earned the prize. That at first he was pretty sure the Turing machine's behavior was simple enough that he could prove that it wasn't universal. But then, as he studied it, he realized that there were little bits of behavior that were more complicated. And it was with these that he managed to show universality. Establishing a wonderful monument in the computational universe--a marker at the edge of universality for Turing machines.
|
http://csua.com/feed/