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."

Comments

Re:Sounds like...

[Anonymous Coward]

Wolfram has previously sued his own employees to keep them from publishing results, and there are many stories about him removing peoples' names from credits.

Perhaps this is the only way he can now get creative people to work on problems like this.

No Halting State

[sugarmotor]

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

Re:No Halting State

[drgonzo59]

If it can emulate a known tag system proven to be a UTM then it is also a UTM. But of course, if you show that it can emulate your typical basic CPU you can also claim it's a UTM. The tag system is easier... I think.

But the larger question is "so what?". So what if it is? When he found the (2,5) system to be, I don't recall the scientific comunity awarding him a Nobel Prize. No matter how much he can run his rule 110 he will not come up with animals, humans or planets. But the whole implication is that that's how "it" happened.

I'll admit, I was one of the suckers who bought NKS before it was put online for free. I read it all -- it reads like bedtime story book. Wolframs "proofs" are mostly just statements like I strongly believe..., I am quite convinced... and look at the pretty pattern I just made! and so on. The most interesting thing was the appendix where he lists some the results and publications of actual scientists (you know the ones that don't define their own "new science" and then by definition become "scientists"...). I whish he would have made the appendix the main part of his book and added his "beliefs" as an appendix.

Of course, he has loads of cash to just sit around and create "cool" patterns and then have a bunch of followers cheering each other on as they play with CA -- it's like they have their own little world, their contests, conferences, classes and so on. Can you say the word "cult" ?

Wolfram and Hart?

[stonedcat]

Upun seeing the title did anyone else think great evil? http://en.wikipedia.org/wiki/Wolfram_%26_Hart

Cult of NKS

[drgonzo59]

Let's see what Wolfram's NKS and Scientology have in common.

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... ;-)

Re:Cock & Balls

[telso]

You're right: objects in nature are so amusing.

Arrow of time is reversed in CA

[hajus]

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.

Re:Arrow of time is reversed in CA

[Aris Katsaris]

Interesting thought.

But since CA represent perfect causal determinism, doesn't that mean we people have the time of arrow backwards ourselves when applying it to our own universe? Instead of the past causing the future, the future causes the past.

The reason we don't know the future for sure, is for the same way that we can't tell for certain which of a number of potential preceding causal states created the "current" state in a CA.

Re:Arrow of time is reversed in CA

[Anonymous Coward]

1: You can add randomness to a CA, it doesn't even have to be pseudorandom if you hook your PC up to a geiger counter for seed values.

2: It's possible to define sets of CA rules such that you can know the past perfectly. For instance, for each step you can enlarge the grid, copy the current state to the new area, and "freeze" it so it doesn't evolve any more.

Re:Arrow of time is reversed in CA

[Anonymous Coward]

Instead of the past causing the future, the future causes the past.

Or to put it another way, causality is a tree with its root at the big bang (one possible state, zero bits of entropy) and its leaves at the myriad possible heat deaths of the universe (many possible states, many bits of entropy).

Every fork in the tree represents a random quantum event. If you follow the tree from root to leaf, moving forward in time, there's no way to predict where you'll end up. But if you follow it from leaf to root, there's only one path. The universe is deterministic in reverse.

The strange thing about Turing machines is they're deterministic in the other direction, from root to leaf - they move forwards in time, but they destroy information, because the output of a calculation has less entropy than the inputs. If you multiply two numbers there's only one possible product. But the product has at least one pair of factors. So there are more input states than output states - the calculation reduces entropy. Think of the inputs as branches of the tree, and the output as the fork where the branches meet (or part). The calculation moves from leaf to root, but meanwhile the machine doing the calculation moves forward in time, from root to leaf. So a Turing machine is like a mirror: it shows you a little world, but it's a world where everything is reversed.

Re:don't even try

[muuh-gnu]

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.

Re:There may be more here that I don't see

[Dster76]

I feel for you, but I have a background in computability theory and I've decided, after looking at the problem page (and not having read any of Wolfram's other stuff) that the challenge is

• 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.