For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function
Katsunobu IMAI Akihiko IKAZAKI Chuzo IWAMOTO Kenichi MORITA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/03/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Cellular Automata)
cellular automata, logical universality, number-conservation,
Full Text: PDF(393.3KB)>>
A number-conserving cellular automaton (NCCA) is a cellular automaton (CA) such that all states of cells are represented by integers and the sum of the cell states is conserved throughout its computing process. It can be thought of as a kind of modelization of the physical conservation law of mass or energy. It is known that the local function of a two-dimensional 45-degree reflection-symmetric von Neumann neighbor NCCA can be represented by linear combinations of a binary function. In spite of the number-conserving constraints, it is possible to design an NCCA with complex rules by employing this representation. In this paper, we study the case in which the binary function depends only on the difference of two cell states, i.e., the case in which the function can be regarded as a unary one and its circuit for applying rules to a cell only need adders and a single value table look up module. Even under this constraint, it is possible to construct a logically universal NCCA.