Simple Computation-Universal Cellular Spaces
Alvy Ray Smith · Journal of the ACM · 1971
The specialization of the theory of cellular spaces (cellular automata) to those spaces which compute partial recursive functions is presented.Neighborhood reduction and state-set reduction are shown to be particularly simple in this special theory, and one dimension is proved to be sufficient for computation universality.Several computation-universal cellular spaces (CUCS's) are exhibited which are simple in the sense that each cell has only a small number q of states and a small number p of neighbors.For example, a 1-dimensional CUCS with pq = 36 is presented.Two quite different proofs of the existence of a I-dimensional CUCS with only two neighbors are given.Finally, one of the theorems derived is used to settle three open decidability questions.