It is perhaps ironic that two weeks after releasing what is probably the single most complex computational system ever constructed, we are today announcing a prize for the very simplest of computational systems.
The prize is related to a core objective of the basic science of NKS: to map out the abstract universe of possible computational systems.
We know from NKS that very simple programs can show immensely complex behavior. And in the NKS book I formulated the Principle of Computational Equivalence that gives an explanation for this discovery.
That principle has many predictions. And one of them is that the ability to do general-purpose computing—to be capable of universal computation—should be common even among systems with very simple rules.
Today’s CPUs have millions of components. But the Principle of Computational Equivalence implies that all kinds of vastly simpler systems should also support universal computation.
The NKS book already gives several dramatic examples. But the purpose of the prize is to determine the boundary of universal computation for a particularly classic type of computational system: Turing machines. Continue reading