FAQs

The Prize

Can anyone enter for the prize?
Yes. And at least in principle the prize could be won by someone without any formal education in computer science or mathematics. But any valid proof will require detailed arguments--and will probably be at least equivalent to a good master's thesis in computer science or mathematics.

Who do you expect will win the prize?
Of course we don't know. But we think it's about equally likely that it will be a professional researcher or academic (probably a mathematician, theoretical computer scientist or perhaps a physicist), and that it will be an "amateur."

How long do you expect it will take?
It's very unlikely that there's a really easy solution. Stephen Wolfram worked on it for a while, and so have some other researchers. But we think it's possible someone could find a solution with a month or two of work. And we are hopeful that the prize will be won within a couple of years.

How will you tell if a proof is correct?
The best case would be a universality proof where there is an explicit compiler that runs at reasonable speed, that can compile a wide range of possible programs.

Any tips on how to win the prize?
Do experiments! Use Mathematica to do computer experiments, searches and the like. See what you find. Build up your intuition. Tag systems may be the most likely ones to emulate. If the machine isn't universal, number theory may be the most likely field to help "decode" it.

What if this Turing machine is not universal?
Then we'll know the threshold for universality is a little higher. And perhaps there'll be another prize for a 4,2 or 2,4 machine (see page 708).

Relation to NKS

What is NKS?
It's the approach to science pioneered in Stephen Wolfram's 2002 book A New Kind of Science ("NKS" is the acronym for the book title). At the core of NKS is the idea of exploring the "computational universe" of possible programs--and the discovery that even very simple programs can show immensely complex behavior that, for example, mirrors many systems in nature. Just as physics studies physical systems and biology studies biological systems, the core of NKS is the study of systems in the computational universe.

How does the prize problem relate to NKS?
It provides an interesting milestone in NKS's effort to survey the computational universe--helping to define the border of where sophisticated computation and sophisticated behavior can occur in systems with simple rules.

Are there other unsolved NKS problems?
Yes, lots and lots. Shortly after the NKS book came out, Stephen Wolfram started to make a list of some of them. You can find them here. Unfortunately, he only got to the beginning of Chapter 4 (out of 12) in listing problems. We've been hoping he'll find the time to go further....

Are there similar NKS problems?
Yes. Probably the most striking is a proof (or disproof) of the universality of the rule 30 cellular automaton. Another, probably simpler, would be a proof of universality, or more likely a proof of non-universality, for rule 54.

Is this the first NKS-related prize?
Yes. But if it goes well, there will probably be more.

Why did you pick this problem for the first NKS-related prize?
Because it's important, yet seems within reach. The universality of rule 30, for example, seems much more difficult.

How can I learn more about NKS?
Read the NKS book. Come to an NKS conference. Come to the NKS Summer School.

Background Questions

Why is this problem important?
Because it helps to define the boundaries of computation--giving information on just how simple a system can be a universal computer. It's also in a sense a classic problem. Turing machines have been around since 1936, yet we still don't know what the simplest universal one is.

Are there practical applications?
Quite possibly. If the prize Turing machine is universal, then it can in principle be used to do arbitrary computations. And because its rules are so simple, it's quite conceivable that they could be implemented directly in something like a molecule.

When did Stephen Wolfram find this Turing machine?
His records indicate that it was around 3 am on May 18, 1994--the result of pruning an exhaustive search of all 2,3 Turing machines. Back then, the search took several hours of computer time. Wolfram's programs run unchanged today, but now they take only a few seconds.

Where can I discuss the problem?
It's being discussed online in the "pure NKS" section of the NKS Forum. It'll also be discussed at NKS conferences.

Technical Questions

Don't we already know that Turing machines can be universal?
Of course! But this prize is about showing that a particular Turing machine, with particular rules, can be universal.

Does your Turing machine halt?
No. Like most real computers, it doesn't have a halt state; it just keeps computing forever. "Results" can get "read off" when the machine "says" it's ready by exhibiting some predefined behavior.

What definition of universality are you using?
The standard one appropriate for unbounded computations. It's the same as in the NKS book. See Technical Details.

Is this the only 2,3 candidate for universality?
As mentioned in Technical Details, there are various similar and directly equivalent 2,3 machines. For many of the 2,3 machines, it's fairly easy to prove that they cannot be universal. But for some it's not absolutely clear.

How do you measure "simplicity" of a Turing machine?
As with all such things, there is some arbitrariness. Roughly, one wants to measure the amount of information needed to specify the rule--or the number of rules one would enumerate before reaching this one. A common way to assess this is to look at the total number of cases in the rule, which is equal to the product of the number of states and colors. (One can also subtract "inaccessible" cases.)

Do you expect the proof to be very specific to this particular machine?
In some aspects, undoubtedly. But we think it's likely that there'll be general methods or ideas developed that'll apply to a variety of systems with simple rules.

Could the prize problem be unsolvable?
Questions about equivalences of machines certainly can be formally undecidable. And it is conceivable that a statement of universality or lack thereof could, for example, be independent of the standard mathematical axioms of arithmetic--though this seems unlikely. It is more likely that the prize problem will turn out to have some form of equivalence to a longstanding unsolved problem in mathematics, such as the 3n+1 problem.

Is there a halting problem for the prize Turing machine?
The machine does not have a halt state, but there are analogs of the halting problem that ask whether the machine achieves particular configurations. Showing that any such problem is undecidable is tantamount to proving universality, but does not strictly achieve this.

Where can I find more information on Turing machines and universality?
There's a list of references at the end of Technical Details.