Slashdot Mirror
Wolfram Offers Prize For (2,3) Turing Machine
An anonymous reader writes "Stephen Wolfram, creator of Mathematica and author of A New Kind of Science, is offering a prize of $25K to anyone who can prove or disprove his conjecture that a particular 2-state, 3-color Turing machine is universal. If true, it would be the simplest universal TM, and possibly the simplest universal computational system. The announcement comes on the 5-year anniversary of the publication of NKS, where among other things Wolfram introduced the current reigning TM champion — 'rule 110,' with 2 states and 5 colors."
One of the colors must be blue so it can emulate Windows.
...he's given up on proving it himself.
Sheesh, evil *and* a jerk. -- Jade
It'll take me some time.
I can disprove it. It will take me some time.
I can disprove it. It'll take me some time.
I can disprove it. It will take me some time.
Is it just me... or is this graph not family-appropriate?
I was disappointed that Wolfram's book A New Kind of Science wasn't something like a Scientology cult. He would have been the awesomest cult leader!
'rule 110'? Come on, that's so much less interesting than 'rule 256'.
There is no rule 265, so, I fixed it for you...
Its way less interesting then rule 34.
The description states that the machine has no halting-state.
I couldn't make out what is to be interpreted as the result of a particular computation of this machine.
Seems like a pretty important detail.
Anyone know?
Stephan
http://stephan.sugarmotor.org
I have a truly marvellous proof of this proposition which this comment is too narrow to contain.
Hmmm, I wonder whether he'll sell any more books as a result of this: From the website: There is a large amount of relevant material in A New Kind of Science.
Sig (appended to the end of comments you post, 120 chars)
I don't understand a word of the summary.. or the article.. But I'm going away to research the topic extensively, and when I get back you can all be assured I'll have opinions on it... Loud opinions!
1. Both closed self-contained, self-referencial systems. ... "This is the new kind of science, old science is obsolete"
2. Both venerate a person: Wolfram and L. Ron Hubbard.
3. Both have this "us" versus "them" mentality.
4. Both have their beliefs and ideas disregarded and ridiculed by the most sane individuals (this just reinforces the cult group cohesion).
5. Both have exclusive facilities & training (NKS Summer School), special meetings and conferences for the members. I don't know...looks like a cult to me... ;-)
The problem I have with CA being proposed as a model of a reality is that the arrow of time in CA seems to be backwards. In our reality, we know the past, but the future is uncertain. In cellular automata, the future can be predicted perfectly, but the states which were used to get to the current state are ambiguous. Large grids of such give the illusion of life (such as behaviour of predator/prey) but only a macroscopic scale even though time goes backward. But the arrow of time becomes very visible when the cells are focussed in on. If you decide to look at it in reverse time to satisfy the microscopic view, you don't get that feeling of life at the macroscopic scale.
Crazy NKS "goodness" for your reading "pleasure": here .
Trust me, even if it is free, after reading it, you'll want your "free" back.
".. a rare blend of monster raving egomania and utter
a r-automata.html
batshit insanity"
Cosma Rohilla Shalizi on S.Wolfram, A new kind of science
http://cscs.umich.edu/~crshalizi/notebooks/cellul
Microsoft Research Labs has 221 proofs to choose from. 85 proofs are related to Mathematics, 115 proofs are related to Alan Turing himself and 21 are mostly general proofs on anything. Also, thay have 43 proofs on those little cells that combine togather into tapestry patterns.
839*929
The nonsense is free online. Wow, now millions of people can read it, waste time ...and make fun it.. hopefully. Crazy NKS "goodness" for your reading "pleasure": here .
Trust me, even if it is free, after reading it, you'll want your "free" back.
You didn't actually read the damn thing, did you? I'm getting really tired of this mindless NKS bashing, no matter how fashionable it is. A book that was largely favorably reviewed in Notices of the American Mathematical Society cannot be 100% nonsense, can it really? I find it amusing that those who are most critical of NKS are almost never real scientists.
There are some severe flaws with NKS. The fundamental philosophical claims are highly doubtful, the "new science" mentioned in its title does not live to its name, the egomaniacal tone, the passing off of other people's hard work as Wolfram's own, the revisionist history, etc. But that said, there is a lot to enjoy in the book. The footnotes are worth the price of a copy on their own, as they are in many ways one of the best exposés of the history of the 20th century focusing on computer science, mathematics and physics I have ever read.
I knew a lot about CAs and discrete models before reading the book, most likely more than you know, or will ever know, and yet I really did learn a lot from it. You just have to be intelligent and well-versed enough to be able to separate the wheat from the chaff. Maybe that's your real problem with the book?
I don't see your point. Mathematicians have offered prizes before for solving problems. Paul Erdos is the most famous of these and his prizes were very successful IMHO at inspiring young mathematicians to investigate the combinatorial and number theory problems that Erdos was interested in. Even if Dr. Wolfram is grandstanding, he offers good money in return. My take is that $25k is roughly six to nine months of postdoc. Not a bad return.
So, in summary, I see Wolfram here using a proven method for getting math results that he is interested in.Knowing how self-congratulatory and megalomaniac Wolfram is, he will also throw out any proofs which:
1. Arent done or simulated using Mathematica, so he cant use them to further advertise Mathematica.
2. Don't cite his book "A New Kind Of Science" as primary and most important reference, which is itself more of an Mathematica scam, then "A Kind of Science" at all.
And the person that made the proof of what is claimed in the summary was Matthew Cook, not Wolfram himself, Wolfram sued him because he presented his proof in another conference (can you believe what a jerk?).
Of course the person that makes this proof will have to concede every right to Wolfram and therefore in some way the 25K are just a payment for such intellectual property.
And the name removing has been mostly due to his book A new kind of science, where he "comes up" with several ideas that have been created by other authors. I would like to *believe* he makes the typical Master or junior PhD error of not looking hard for the current work but other people believe he just wanted to plagiarize other's people ideas.
Ubuntu is an African word meaning 'I can't configure Debian'
"For the benefit of society we should be funding research that can best serve society."
;-) to have a mixed bag of research/sponsoring. To me, the more variation you have in research (and fields), the more chance you have of cross-fertilisation between those fields and research, and THAT is best for society. If all things were just for commercial and profit gain, or all things were just academic research, I think society as a whole would be worse off.
That would imply that one would know in front what research can best serve society.
This is rather contentious and doubtful; first of all, it is rather arbitrary as to define what is 'best' for society, and furthermore, it's impossible to know what may come from that research in terms of future possibilities - or while not useful themselves, may lead to advances (or in combination with other research) that would otherwise have been lost. The theorethical research of the laser, for instance, was made ages before anything useful could be done with it - but still it was necessary to have our practical applications today. I imagine, however, that in the early days where the research was academical, people would have considered the research worthless too. Much like the CERN is considered by some to be a complete waste of time and money which doesn't help society.
I've always thought it to be best (also for society
But then again, as I said, the 'best' part is rather arbitrary and next to impossible to prove one way or another. (Not that I do not agree that sometimes, money IS being wasted on useless research (be it commercial or academic), but my viewpoint on when it's wasted will often differ with that of someone else).
--- "To pee or not to pee, that is the question." ---
There are some severe flaws with NKS.
You bet!
The fundamental philosophical claims are highly doubtful
Check.
Check
the egomaniacal tone
Also "Check"
the passing off of other people's hard work as Wolfram's own, the revisionist history
One more big "Check". -- This is what did it for me. I wish he made the appendix section the main part of the book. That's where he actually mentioned who did what before him and I found the examples there more interesting than Wolfram's prose + pictures. Yes, as scientist I am very sensitive and biased when it comes to passing someone's work as your own, that is very much a "no-no" in the scientific community. The only time the rest of the world hears about the scientists is when they discover something really amazing or plagiarize.
Overall, was the reading insteresting?, -- it was alright for me. I learned some new things as well (but mostly things others did that W. re-did in Mathematica) about CA, tag systems, fractals and such. But it was anything but a "New Kind Of Science". It wasn't "New" (just re-packaged) and it wasn't a "Science" it was just prose. Apart from few examples, W.'s "proofs" consist of phrases like "I strongly believe X", "I am quite confident that Y" and "Look at the pretty picture I generated!".
Trust me I tried to like it: I paid money for the book and spent time reading it, I didn't want o believe that I somehow 'wasted' it, but in the end I have to be honest to myself and say 'no' it isn't what it claims to be and 'yes' I wish I hadn't spent the time and money buying it.
I don't see your point either. I am doing a postdoc right now and they
are paying me because they suppose I will do something good in this time.
Even if I do not produce incredible results I will get paid.
Wolfram instead, pays you only if you succeed in something that is very difficult
(if he has not solved it by himself)
No my dear, this is mass extortion: he gets all the advantages and no drawbacks:
- he seems to be generous!
- he sells more copies of his horrid science fiction book;
- he gets dozens of smart guys working on it;
- he pays only if someone succeeds;
- he just spends 25.000$ and also gets a lot of publicity.
I have to admit, he's really smart. Making money.
It may be interesting to those who aren't just here to bash Wolfram that this offer to provide a prize for a proof of one of his key conjectures in A New Kind of Science (NKS) comes only seven weeks after another key conjecture was disproved. (The fact that that disproof was brought to public notice by the NKS Forum moderator might suggest that the ongoing NKS project is happy enough for results to fall whichever way they will.)
On a visit to Champaign-Urbana in the late 1980s, still before he officially started on NKS, Wolfram took me through where he felt his cellular automata research was headed which hinted at some of the inferences he would eventually draw from his mountains of research data. That was even before the Santa Fe Institute paper which was foolishly read as retreating from the edge of chaos-border of order which had briefly been the focus of the quest for the source of emergent complexity during the 1980s.
The resources Wolfram is bringing to the table are significant and have certainly helped put complex systems back in the spotlight after far too many of the first generation of researchers were seduced by the marginal returns they could get by applying their methods to the derivatives market, no matter whether their methods made a significant difference or not.
The downside of continuing to focus on the simplest possible mechanisms (Wolfram calls them 'programs') as the source of a critical threshold is that all those much sought after proofs of universality, from the early one for Conway's Life on, are vast feats of engineering and thus make no useful progress towards the implicit goal of helping to explain how we/anything got here in the first place.
So I'll keep playing with my own idiosyncratic program to explore a bit deeper in that narrow and difficult transition region between order and chaos, but might be tempted to have another look at Mathematica's increasing support for such research once it is available via CP6AN.
-- Our systemic servants do not good masters make.
- perfectly sensible, and,
- quite hard.
He describes a Turing machine with a language consisting of three symbols (his use of colors is annoying), two states, and six state transitions. It's much easier to follow if you ignore all the pictures and just read the set description of his machine. The third '1' in the output triples means 'move left' and '-1' means 'move right'.To prove that this Wolfram's machine W is universal, provide a construction where you take an arbitrary Turing machine T_k, and an input to that machine n, and generate an encoding e such that T_k(n) = W(e), or W(e) yields a verifiable loop if T_k(n) does not halt.
On the other hand, to prove that W is not universal, show how the assumption that it is leads to contradiction.