- Link:
- http://hdl.handle.net/1721.1/6891
- Collection:
-
- Creator:
- Banks, Edwin Roger
- Format
- 4348671 bytes
- Format
- 3048133 bytes
- Format
- application/postscript
- Format
- application/pdf
- Language
- en_US
- Relation
- AITR-233
- Description
- A cellular automaton is an iterative array of very
simple identical information processing machines called cells. Each
cell can communicate with neighboring cells. At discrete moments of
time the cells can change from one state to another as a function
of the states of the cell and its neighbors. Thus on a global
basis, the collection of cells is characterized by some type of
behavior. The goal of this investigation was to determine just how
simple the individual cells could be while the global behavior
achieved some specified criterion of complexity ??ually the ability
to perform a computation or to reproduce some pattern. The chief
result described in this thesis is that an array of identical
square cells (in two dimensions), each cell of which communicates
directly with only its four nearest edge neighbors and each of
which can exist in only two states, can perform any computation.
This computation proceeds in a straight forward way. A
configuration is a specification of the states of all the cells in
some area of the iterative array. Another result described in this
thesis is the existence of a self-reproducing configuration in an
array of four-state cells, a reduction of four states from the
previously known eight-state case. The technique of information
processing in cellular arrays involves the synthesis of some basic
components. Then the desired behaviors are obtained by the
interconnection of these components. A chapter on components
describes some sets of basic components. Possible applications of
the results of this investigation, descriptions of some interesting
phenomena (for vanishingly small cells), and suggestions for
further study are given later.
- Visits:
- 1
- Access:
- Instructions in case access is denied
Site powered by:
