# 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

# Descriptors:

# Subject Categories:

- Bionics