Information Processing and Transmission in Cellular Automata

Item

Title
en_US Information Processing and Transmission in Cellular Automata
Creator
en_US Banks, Edwin Roger
Date
2004-10-20T20:04:43Z
Date Available
2004-10-20T20:04:43Z
Date Issued
en_US 1971-01-01
Identifier
en_US AITR-233
uri
http://hdl.handle.net/1721.1/6891
Abstract
en_US 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.
Extent
4348671 bytes
3048133 bytes
Format
application/postscript
application/pdf
Language
en_US
Relation
en_US AITR-233
MAC-TR-081
Item sets
AI Technical Reports (1964 - 2004)