First my prejudices about Wolfram. A New Kind of Science (ANKS), the book by Wolfram, is a mixed message. It is not new at all, the text is filled with intellectual arrogance (even the copyright legalese is full of itself), it is a thinly veiled advertisement for Mathematica. I'm mostly in agreement with reviewers of the book (just google for them). But those reviews tended to be entirely negative and really do not say anything at all positive about it of which there certainly is something when the negative is removed (but of course that positive remainder is nowhere near what I think Wolfram thinks it is). There's a lot of pictures (mostly cellular automata) which I think is a good thing. It is a popularization that has substantive math (but just to put in a dig to ANKS, it is no Goedel, Escher, Bach which even then has its own problems). Wolfram gives in print a number of mappings (in Mathematica) among the Church-Turing complete formalisms, which, though not particularly earth shattering, is a nice thing to see in print (as is said in one of the options for reviewing TCS papers, it is workman-like (not toward the top of the goodness rating)). I'll stop there, I could go on and on...
As to the 2,3 proof:
- the automaton is not a Turing Machine. It's in a formalization, (cellular) that is -similar- but not the same. So, without knowing well the mapping between the two, I can't say if the number of states and symbols is preserved, and even if so, if the mapping preserves the appropriate relevant properties that I haven't thought of.
- The proof seems to use Mathematica to generate and test cases. Excellent! I'm totally on board with this as a proof method (I suspect that others might have problems with it).
- The proof was submitted, not to a journal for peer review, but directly to Wolfram's company. And it seems that though a committee of 'names': Lenore Blum, Greg Chaitin, Martin Davis, Ron Graham, Yuri Matiyasevich, Marvin Minsky, Dana Scott, Stephen Wolfram, (-all- gods, even Wolfram) is supposedly the review committee, it doesn't seem as though that anybody on the committee actually reviewed the paper (at least that is the impression I got from the FOM thread, of which Davis and Minsky (the two leader of the gods for this subject) are members).
- To add sarcastic comment, big deal. Yes it's cool, in the sense that optimization of results is always cool, but again, it's not a big theoretical advance (it's not a small one) it's just engineering a more efficient example. "I can name that tune in 5 notes", "I can name it in 4". Big deal, just -naming- it is what counts, all the rest is shaving off constants. Yes, there is a one rule TRS that is universal (Dauchet (ugly proof by the way)), and there is a single axiom that defines 'group' (rather than the usual 3), and there is a diophantine equation with blah variables of degree blahdiblahblah that sniggertiflibbet. All good details to know about (and to know that they are optimal, rather than just an improvement), but hardly important by any means (frankly I'd be happy myself to prove something of that nature, but I'd still realize the lack of importance.
- Wolfram, in his msg to FOM says: I remember that when I first heard about universality in the Game of Life in the early 1970s, I didn't think it particularly significant; it seemed like just a clever hack. But a few decades later---after building up the whole framework in A New Kind of Science (http://www.wolframscience.com), I have a quite different view. I now think that it's extremely significant just how widespread---or not---computational ability is. My thinking has gone in quite the opposite direction, at least for this particular problem (that is, it's not a general application to proofs that constants are just 'icing' (it might be, I don't know, I'm allowing the possibility), just for this problem can I justify my own opinion against Wolfram's) Somehow, figuring out constants (like a machine that has 1 less state than yours, used to seem doable to me, and reasoning by meta knowledge (I believe I know more than I did), I figure that is a simpler type of problem). For example, there's one hour of your average automata class that is spent on pages blah blh blah of Hopcroft and Ullman (not 'and Motwani' because it was removed in the later edition, for reasons probably of -unimportantness-) where in extremely dense mathprose, it is proved that a PDA can be converted into a PDA recognizing the same language but requiring only a -single- state. At which one can reasonably remark 'cool, but so what?', with the natural response 'What do you mean 'so what?' ?'. Well the answer (to which 'so what?' I'm having trouble figuring out) is 'ok, that might simplify representations but it happens not to result in a more efficent parser (though of course it might have resulted in something useful, it just happens that it didn't)
- just to be cynical about the whole thing some more, it just seems like some big ploy, more self-aggrandizement (no, Wolfram didn't prove anything (if anybody did!) but he had the intuition that his example of a 2,3 'turing machine' (lower case but with scare quotes) was universal (and so he's a genius because he can 'see' what others have to prove). This is another conversation about hoaxes, Sokal, post-modernism and Stolzenberg's defense (that gibberish may be your fault, not the speaker's).
- In some sense, I hope I'm wrong, I hope that the proof is right and that Wolfram's claims are on target and his new philosphy is both useful and accepted...but, it just doesn't have the right taste for that, it all seems like delusions of grandeur crankery.
- anyway, congratulations to Alex Smith, $25K ain't nothing.
- like all conscientious mathematicians, I've skimmed the article twice, looked at one or two pages a little closer, looked for misspellings and found none, noted Vaughan Pratt's FOM comment about an egregious logical solecism, looked at the table of contents again (the pages don't really have page numbers), read the epilog (excellent idea..every proof should have a summary of how the proof was found), looked at the conclusion paragraph which was more technical than conclusive, and then went to lunch and haven't looked back at it yet with a totally committal '
looks like a proof to me' hoping someone else will actually care about the details (the technical differences put me off, that is, it's in cellular automaton notation rather turing machine notation, and getting past that (little, tiny, I don't know) but is just that little bit too much to be worth it. - Arghh. Update (there's always something left to say).Wolfram also said: One thing that's come out of my efforts in this direction is what I call the Principle of Computational Equivalence. It's a fairly bold hypothesis about which there's much to say (e.g. http://www.wolframscience.com/nksonline/chapter-12 ). This 'PCE' bears some superficial comparison with the Church-Turing Thesis, either as similar but essentially different or as a poor attempt at rewriting it. It comes out sounding rather...trivial, another 'so what?', a 'didn't-Douglas-Adams-make-fun-of-this-years-ago?' idea. So 'fairly bold'? Sure, mind blowing if you're fifteen years old (I apologize to all fifteen years olds with mind blowing ideas that turn out to be disparaged by some old guys who think they've seen it all). And (another) frankly, all that this really -explains- is some patterns on some sea shells? at least DNA has some vague correspondence with a TM tape.
- Another update. more FOM comments, one from Hector Zenli, the lead of the '2-3 TM' contest team: Concerning the prize committee, we did not expect them to go through the details of the proof but to support the reviewers on technical issues related to their fields of expertise. We would have been delighted to have had them spend more time on the proof but that wasn't our expectation. OK, so far kinda weak...isn't review of truth supposed to be impartial? Isn't this playing with concept names (and authorities' names)? The prize committee with the 'gods' (the expert authorities) aren't the actual reviewers. And 'delighted' sounds like its covering up lack of participation. How many submissions were there? What was the workload? What was the 'prize' committee really expected to do (I want to hear it from the prize committee). But it was Wolfram staff (my's emphasis) who did the hard work to achieve a satisfactory level of verification (between revisions and revision requests) Oh. And I mean it to sting.
