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

Katsunobu IMAI; Akihiko IKAZAKI; Chuzo IWAMOTO; Kenichi MORITA

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

Katsunobu IMAI, Akihiko IKAZAKI, Chuzo IWAMOTO, Kenichi MORITA

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E87-D No.3 pp.694-699

Publication Date: 2004/03/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cellular Automata)

Category

Cite this

Copy

Katsunobu IMAI, Akihiko IKAZAKI, Chuzo IWAMOTO, Kenichi MORITA, "A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function" in IEICE TRANSACTIONS on Information, vol. E87-D, no. 3, pp. 694-699, March 2004, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e87-d_3_694/_p

Copy

@ARTICLE{e87-d_3_694,
author={Katsunobu IMAI, Akihiko IKAZAKI, Chuzo IWAMOTO, Kenichi MORITA, },
journal={IEICE TRANSACTIONS on Information},
title={A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function},
year={2004},
volume={E87-D},
number={3},
pages={694-699},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function
T2 - IEICE TRANSACTIONS on Information
SP - 694
EP - 699
AU - Katsunobu IMAI
AU - Akihiko IKAZAKI
AU - Chuzo IWAMOTO
AU - Kenichi MORITA
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2004
AB - 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.
ER -