A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function

Katsunobu IMAI  Akihiko IKAZAKI  Chuzo IWAMOTO  Kenichi MORITA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.3   pp.694-699
Publication Date: 2004/03/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Cellular Automata)
Category: 
Keyword: 
cellular automata,  logical universality,  number-conservation,  

Full Text: PDF(393.3KB)>>
Buy this Article




Summary: 
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.