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
can you please explain for the guys a bit slower than yourself...
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!
Upun seeing the title did anyone else think great evil? http://en.wikipedia.org/wiki/Wolfram_%26_Hart
You can't take the sky from me.
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.
I have discovered a truly marvelous proof of killer sig, which this margin is too narrow to contain.
Way, way, way less interesting. But more importantly, the first rule of /b/: DON'T EFFING TALK ABOUT /B/.
Crazy NKS "goodness" for your reading "pleasure": here .
Trust me, even if it is free, after reading it, you'll want your "free" back.
I am really sick of this guy's way of doing "science".
He came out of the scientific community after publishing some
witty papers and entered in his own ivory tower with a lot of
money coming from that awful piece of software and now that
he's not able to overcome this problem shouts to everybody:
"Hey! I'll give you 25k $ if you solve this!"
If I were really bright on that subject and able to solve it
I would just publish on a regular paper and send him an email
saying: "Hey Mr Wolfram, by the way I solved your problem, now use
your dirty 25.000$ to buy another bright postdoc's best ideas and
say that they are yours!"
Descend on planet Earth Mr Wolfram.
".. 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
Does anyone, after reading TFA (I know, not that common on slashdot) that we NEED governmental subsidized research? I mean, I know there are those who think the private sector and the free market is the solution to everything (like a financial turingmachine that is universal), but NO private industry wanting to make a profit out of it would ever finance such academic research and work.
This is mainly knowdledge for the sake of knowledge, and companies aren't really interested in that. They would even only *consider* sponsoring such things if a case for commercial applicability can be made.
Take away the state(funding), and academic research is going to suffer big time.
But than again, to those who only see value in earning a profit, this kind of research is pretty useless anyway.
--- "To pee or not to pee, that is the question." ---
If you are not a professional mathematician, I doubt they will even read your proof. For the milennium problems this is even a policy, it is a way to filter out most of the garbage.
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?
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'
sounds like a wolf in sheep's clothing!
New kind of science my ass.
Isn't it weird that such a "renowed" mathematician doesn't even understand entropy?
Given known UTM M and 2,3 TM N, for some input P1 there exists an encoding algorithm that yields P2. Plugging P2 in N, the result is Q2 and there exists a decoding algorithm that yields Q1. Plugging P1 into M yields Q1.
Therefore, if the encoding and decoding algorithms exist and are sufficiently simple as their operation would not justify working out the problem outside of the 2,3 TM then N is a UTM.
Find E & D (the encoding and decoding algorithms, respectively).
"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." ---
You fucking retard, he didn't mention ... He simply mentioned Rule 34. On top of that you can't even spell ... properly. There is no uppercase in ... It is always lower case. You are obviously some pathetic gaiafag that seriously needs to become an hero. I suggest you lurk the fuck moar before trying to act all hard on the interbutts. You don't even know your fucking memes correctly.
... especially as it is YOU that has broken Rule 1 and Rule 2.
I hate fag-bitch retards like you that spoil the good name of
Now STFU retard, go die in a fire and may our Lord Raptor Jesus H Christ show mercy on your unworthy soul.
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.
> The nonsense is free online.
From the FAQ:
"We are considering a future e-book version of NKS, but it is difficult to achieve adequate quality level"
Well, assuming you don't use PDF. I've seen books/papers etc in PDF format and they look fine to me. Whatever can he mean?
If you buy the work, its not really plagiarizing. Its called business.
---- Booth was a patriot ----
Is it necessarily true in our reality that we know the past and the future is uncertain? There are some very interesting theories of space-time involving multiple time or time-like dimensions, e.g. 3,3 spacetime. In these theories, the future and the past are interdependent and probabilistic. According to Carroll the future and past of an event arise from extra temporal properties which we do not otherwise notice. There was an article about 6-d space time here recently
Hey, now. He sai da computer, with 3 colors. Fermat o nly had about 4 l in es (and barely much width) to work with, and the algebraic (negation) proof is seven lines and pretty wide (binomial theorum, unexpanded).
-Drew
Maybe he's not using the pslatex package in LyX. :-)
Presumably, if you could emulate the (2, 5) machine, then this would count as proof, but that can't be the only way to do it, because iteratively we'd need something that can be defined as turing complete to end a chain of emulations. What does Turing complete actually mean? Are there some specific tests?
How about rules 1 and 2?
That story is the _best_ argument FOR public funding.
Wolfram only announces this (rather small) price to get publicity for his NKS bullshit, and sell more books.
So in fact, the whole procedure will actually create a net loss in knowledge and intelligence (people that will work on it get dumber, and dont create useful knowledge in the meantime).
HI O WISE PRINCE. WHT TOOK U SO DAM LONG?
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.
"That story is the _best_ argument FOR public funding."
That's what I said.
"Wolfram only announces this (rather small) price to get publicity for his NKS bullshit, and sell more books.
So in fact, the whole procedure will actually create a net loss in knowledge and intelligence (people that will work on it get dumber, and dont create useful knowledge in the meantime)."
Seen the quality of your counter-arguments, you'd better hope everyone reading your post is retarded.
--- "To pee or not to pee, that is the question." ---
for the authors of BrainF***
arrrg, (like a pirate)
What we do is if we need that extra... push over the cliff, you know what we do?
Marty DiBergi: Put it up to 256.
Nigel Tufnel: ...256 Exactly. One louder.
Hmmm - $25k just about pays for one license for Mathematica. Perhaps he could offer that as an option.
sPh
I read much of NKS; skimmed through the rest. My conclusion: If you immerse yourself in the world of cellular automata for an extended period of time, then you will eventually become convinced that the world *is* cellular automata.
I took a class from Jim Crutchfield and he said the same thing. Apparently Wolfram stole Mathematica to begin with, though his website makes him out to be a child genius that created the program over a long weekend.
Is he in business with a guy name Hart? If so i don't want to know about it.
Remember... A boomerang IS NOT the best way to deliver a bomb.
I see you didn't use your cruise control until about 3/4 the way through. Def a gaiafag, GTFO plox, kthnks
I have read the points he is making, and the example given that he wants some proof related to the issue of Universality, as well as the cell site given. And while I do think I do have quite a bit of intelligence, I do not understand any of this. I don't get what the change states are, and I don't understand what he is trying to solve. I believe there is an old rule - never ascribe to malice what can equally be explained by stupidity - which would apply here.
Maybe I've been spoiled by the cellular automata rules in the (Martin Conway) game of Life, and maybe because of that I don't get this. At least, that's what I am trying to understand, is he saying that eventually the set of rules for these two states have a particular sequence that repeats, so that no matter what state it is in, eventually it will cycle to that state again, or what?
Someone - it might be Kurt Vonnegut - once stated that anyone who can't explain what they are doing to a six-year-old is a fraud. Probably because the average six-year-old is brighter than most adults. So there is the possibility the whole thing is a scam, but if so, he's far to much of a cheapskate to be running it, since most really good scams depend on the greed of the mark. (Read my blog for an example.) But I'm willing to give Wolfram the benefit of the doubt and say that his real problem is that while the subject is extremely esoteric, he has failed to make the issue understandable by the people who would be expected to solve it. Programmers - like myself - are exceptionally good at puzzles, and some - again, like myself (no false modesty here) - are fairly bright and are willing to take on a challenge, the problem is that we as problem solvers have to be able to understand the problem in order to solve it.
I think either he needs to explain what he wants to solve better, or he needs to hire someone bright who can translate what he is trying to determine to others so they can understand it. I think, were he to provide a better explanation of what he is interested in discovering, he'd have a better chance of getting people to try and solve it. This presumes he actually wants a solution and that this is not some advertising scheme to sell more of his books. (If that were the case, he'd really need to throw more money at it. He could always rig the rules such that you can't really win.) But since you could read them on-line I don't see where that's all that much of an issue.
So I'll grant the premise that he is seriously looking for a solution to a legitimate problem. (A "legitimate problem" is one where the person wants a solution, e.g. when I lose my car keys before I'm going to go somewhere I have a legitimate problem.) But he definitely needs to find a way to explain it better if he actually wants it solved, or throw more money at it in order to make people smell blood.
I explain this comment in more detail on my blog.The lessons of history teach us - if they teach us anything - that nobody learns the lessons that history teaches us.
You better watch what you say about us threatening you.
Signed,
The thug in the ski mask hiding in the bush outside your house.
I agree Wolfram's pompous, egocentric self promotion is outright an Insult to many hard working people who did not receive credit for their own insight.
it was alright for me. I learned some new things as well
To me, reading the book allowed me the chance to view a whole other means of mathematical modeling from a coherent and complete viewpoint.
If you filter out his ego, his book is more like a good reference of discrete computational modeling as opposed to continuous functional analysis. In a sense it's what he tries to say with his 'computational equivalence'. He does use self worship and awe to try and sell his opinions as 'truth'. Still, I can't deny the coherence, order and hierarchy to the book. That structure would make the book definitely worthwhile had he given credit to the appropriate people.
From the article:
"...there are at least two ways in which
he has benefited mathematics: he has helped to
popularize a relatively little-known mathematical
area (CA theory), and he has unwittingly provided
several highly instructive examples of the pitfalls
of trying to dispense with mathematical rigor."
(Lawrence Gray, "A Mathematician Looks at Wolfram's New Kind Of Science).
I give credit to the author for a fair evaluation, but I wouldn't exactly call it a favorable review.
If Wolfram wrote "A Pictoral Introduction to Cellular Automata", and left out the hundreds of pages of self-aggrandizing nonsense, it would be factual, useful and no one would complain.
It's my contention that the some of the quirky (and often with very useful side effects) discoveries that make FOSS better come as a result of non-financially biased research/work.
Having said that, FOSS may need IBM right now! (my enemy's enemy is my friend and all that).
... if it were well defined. Instead Wolfram seems to be using a nonstandard, unclear notion of "universality". By any standard definition, no Turing machine without a halting state can be universal. Thus, coming up with a satisfactory proof of "universality" or "non-universality" would seem to serve no purpose besides promoting Wolfram's nonstandard definitions. At the least, he should not describe this gadget as a Turing machine, which definitely implies a particular notion of universality.
You see, the functions computable by Turing machines whose "halting" is defined as some pre-specified infinite loop, identical for all outputs, are the same as the functions computable by regular Turing machines with a privileged halting state. That is why, from the point of computability theory, it doesn't matter that Wolfram's possible universal machine doesn't have a privileged halting state. As a result, the result, positive or negative, would seem less interesting to me, as a researcher in computational complexity. I don't know why you think that a result in computability theory would be of interest to a researcher in computational complexity (beyond both having 'something to do with computers').
Then, you complain that his use of the term "smallest" is unfair.
Which is it?
Again -- "this would be a fun problem to tackle if it were well defined".
It is well defined. And, it concerns whether a machine, which he has introduced, is universal, in a clear, meaningful sense.
Your new complaint, that Wolfram's use of the term "smallest Turing machine" is self-aggrandizing, unfair, and ignores the history of computability is correct, but is nothing new, as far as criticisms of Wolfram go. I saw what was probably the first talk on his book tour for NKOS and I concur on all points.
I'm glad you 'dug deep' to clarify your complaints about Wolfram, and show that you do understand the problem he has posed. Your PhD advisor would be proud!
By the way, when you start to defend yourself by reminding people that you went to MIT, and had a famous advisor, you start to sound a bit like Wol.. oh, now I'm just being cruel.
The meaning of "given set of resources", in complexity theory, is "growth-bounded time and/or space", neither of which are part of the "resources", now meaning "finite but unbounded time and space", of computability theory. Also, believe it or not, there are some models of computation which are universal even though they only use finite resources! I have no idea what you're talking about.
http://www.cs.duke.edu/~reif/paper/games/bounds/p
or
http://www.swiss.ai.mit.edu/~bob/hearn-thesis-fin
First you say that there are models of computation that are
- universal, and
- use finite resources.
A computer that uses finite resources is one, for example, that only ever uses 47 squares on a tape.To give me examples, you refer to models of computation that are
http://www.lrb.co.uk/v29/n10/fodo01_.htmls /books/05/13/0513hofstadter.html
http://www.statesman.com/life/content/life/storie
Since when has it been OK to presume a Turing Machine models the Universe in any way at all? You seem to believe disproving "UTM == Universe" would be shocking. Have I misparsed you?