CELLULAR AUTOMATA THEORY.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1969
- Accession Number
- AD0707442
Entities
People
- Alvy Ray Smith Iii
Organizations
- Stanford University