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 2-dimensional cellular space is intuitively an infinite chessboard, each square of which represents a copy of a single finite-state 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 next-state function, and operates synchronously in discrete time steps with all other cells. In the report the formal definitions for the n-dimensional 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 n-dimensional space, that there is a binary equivalent for an arbitrary cellular space, and that speed-ups 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 non-trivial self-reproducing 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