
Accession Number : AD0707442
Title : CELLULAR AUTOMATA THEORY.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF STANFORD ELECTRONICS LABS
Personal Author(s) : Smith,Alvy Ray , III
Report Date : DEC 1969
Pagination or Media Count : 123
Abstract : A 2dimensional cellular space is intuitively an infinite chessboard, each square of which represents a copy of a single finitestate machine, or cell. The next state of each cell is a function of its own present state and the present states of a fixed number of neighboring cells in a fixed geometric arrangement. Each cell in a given cellular space has the same neighborhood, the same nextstate function, and operates synchronously in discrete time steps with all other cells. In the report the formal definitions for the ndimensional generalization of cellular spaces are presented and the general theory of these spaces as mathematical objects is developed. It is established that there is a canonical class of minimal neighborhoods with n+1 neighbors for an ndimensional space, that there is a binary equivalent for an arbitrary cellular space, and that speedups by an arbitrary integer factor are attainable. In addition, a specialization to those cellular automata which compute that partial recursive functions is presented, conditions for computation are established, and a new proof of the existence of nontrivial selfreproducing machines is given which is both brief and simple. (Author)
Descriptors : (*AUTOMATA, THEORY), RECURSIVE FUNCTIONS, ARTIFICIAL INTELLIGENCE, MATHEMATICAL MODELS, ALGORITHMS, THEOREMS
Subject Categories : Bionics
Distribution Statement : APPROVED FOR PUBLIC RELEASE