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 withi
