Accession Number:

AD0707442

Title:

CELLULAR AUTOMATA THEORY.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CALIF STANFORD ELECTRONICS LABS

Personal Author(s):

Report Date:

1969-12-01

Pagination or Media Count:

123.0

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 n1 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

Subject Categories:

  • Bionics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE