Simple Computation-Universal Cellular Spaces

Abstract

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.