A One-Dimensional Physically Universal Cellular Automaton

被引：6
|
作者：
Salo, Ville [1 ]
Torma, Ilkka [1 ]
机构：
[1] Univ Turku, Dept Matemat & Stat, Turku, Finland
来源：
UNVEILING DYNAMICS AND COMPLEXITY, CIE 2017 | 2017年 / 10307卷
基金：
芬兰科学院;
关键词：
Cellular automaton; Physical universality; Reversibility;
D O I：
10.1007/978-3-319-58741-7_35
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Physical universality of a cellular automaton was defined by Janzing in 2010 as the ability to implement an arbitrary transformation of spatial patterns. In 2014, Schaeffer gave a construction of a two-dimensional physically universal cellular automaton. We construct a one-dimensional version of the automaton and a reversibly universal automaton.
引用
收藏
页码：375 / 386
页数：12
相关论文
共 50 条
  • [1] A one-dimensional physically universal cellular automaton
    Salo, Ville
    Törmä, Ilkka
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2017, 10307 LNCS : 375 - 386
  • [2] A Physically Universal Cellular Automaton
    Schaeffer, Luke
    PROCEEDINGS OF THE 6TH INNOVATIONS IN THEORETICAL COMPUTER SCIENCE (ITCS'15), 2015, : 237 - 246
  • [3] Replication and Shift Representation of One-Dimensional Prototype Universal Cellular Automaton
    Guan, Junbiao
    Chen, Fangyue
    JOURNAL OF CELLULAR AUTOMATA, 2013, 8 (3-4) : 299 - 310
  • [4] Replication and shift representation of one-dimensional prototype universal cellular automaton
    1600, Old City Publishing (08): : 3 - 4
  • [5] One-Dimensional Cellular Automaton Transducers
    Kutrib, Martin
    Malcher, Andreas
    FUNDAMENTA INFORMATICAE, 2013, 126 (2-3) : 201 - 224
  • [6] A Physically Universal Quantum Cellular Automaton
    Schaeffer, Luke
    CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS, AUTOMATA 2015, 2015, 9099 : 46 - 58
  • [7] A quantum cellular automaton for one-dimensional QED
    Arrighi, Pablo
    Beny, Cedric
    Farrelly, Terry
    QUANTUM INFORMATION PROCESSING, 2020, 19 (03)
  • [8] Transients in a one-dimensional probabilistic cellular automaton
    Bhattacharyya, P
    PHYSICA A, 1997, 245 (3-4): : 472 - 484
  • [9] UNIVERSALITY CLASS OF A ONE-DIMENSIONAL CELLULAR AUTOMATON
    JENSEN, I
    PHYSICAL REVIEW A, 1991, 43 (06): : 3187 - 3189
  • [10] A quantum cellular automaton for one-dimensional QED
    Pablo Arrighi
    Cédric Bény
    Terry Farrelly
    Quantum Information Processing, 2020, 19
12345