Simple universal one-dimensional reversible cellular automata

被引：0
|
作者：
Morita, Kenichi [1 ]
机构：
[1] Hiroshima Univ, Grad Sch Engn, Higashihiroshima 7398527, Japan
来源：
JOURNAL OF CELLULAR AUTOMATA | 2007年 / 2卷 / 02期
关键词：
reversible cellular automaton; universality; cyclic tag system;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We study a problem of finding universal one-dimensional reversible (injective) cellular automata (RCAs) with a small number of states. We first give a 36-state universal RCA that operates on an infinite configuration that can simulate any cyclic tag system (CTAG). We then give a 98-state model that operates on a finite configuration and can also manage halting of a CTAG.
引用
收藏
页码：159 / 165
页数：7
相关论文
共 50 条
  • [1] THE STRUCTURE OF REVERSIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA
    HILLMAN, D
    PHYSICA D, 1991, 52 (2-3): : 277 - 292
  • [2] Spectral properties of reversible one-dimensional cellular automata
    Mora, JCST
    Vergara, SVC
    Martinez, GJ
    McIntosh, HV
    INTERNATIONAL JOURNAL OF MODERN PHYSICS C, 2003, 14 (03): : 379 - 395
  • [3] Procedures for calculating reversible one-dimensional cellular automata
    Mora, JCST
    Vergara, SVC
    Martínez, GJ
    McIntosh, HV
    PHYSICA D-NONLINEAR PHENOMENA, 2005, 202 (1-2) : 134 - 141
  • [4] Hybrid one-dimensional reversible cellular automata are regular
    Bingham, Jesse
    Bingham, Brad
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (18) : 2555 - 2566
  • [5] Grids and universal computations on one-dimensional cellular automata
    Yunes, Jean-Baptiste
    NATURAL COMPUTING, 2012, 11 (02) : 303 - 309
  • [6] Grids and universal computations on one-dimensional cellular automata
    Jean-Baptiste Yunès
    Natural Computing, 2012, 11 : 303 - 309
  • [7] Achieving Universal Computations on One-Dimensional Cellular Automata
    Yunes, Jean-Baptiste
    CELLULAR AUTOMATA, 2010, 6350 : 660 - 669
  • [8] UNCONVENTIONAL INVERTIBLE BEHAVIORS IN REVERSIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA
    Tuoh Mora, Juan Carlos Seck
    Gonzalez Hernandez, Manuel
    Martinez, Genaro Juarez
    Chapa Vergara, Sergio V.
    McIntosh, Harold V.
    INTERNATIONAL JOURNAL OF BIFURCATION AND CHAOS, 2008, 18 (12): : 3625 - 3632
  • [9] REVERSIBLE SIMULATION OF ONE-DIMENSIONAL IRREVERSIBLE CELLULAR-AUTOMATA
    MORITA, K
    THEORETICAL COMPUTER SCIENCE, 1995, 148 (01) : 157 - 163
  • [10] On the size of the inverse neighborhoods for one-dimensional reversible cellular automata
    Czeizler, E
    THEORETICAL COMPUTER SCIENCE, 2004, 325 (02) : 273 - 284
12345