Conceptual Background for the Quad Prize
Tommaso Toffoli
The Quad Prize, to be awarded in coordination with the Automata-2008 workshop, seeks to encourage the filling of a gap in our imagination of the simplest models of computation, and will be awarded to the first submission that will either exhibit a computation-universal 2-state cellular automaton on a 2-dimensional, 2 × 2-neighborhood—or on the contrary prove that none exist within that class. Short of that, a partial prize may be awarded for a significant partial result. Administrative details are given elsewhere; here we clarify the scientific/technical aspects of the competition.
Keywords: Cellular automata; universal computation; minimal realization.