Decidability and undecidability in cellular automata

被引:7
作者
Kari, Jarkko [1 ]
机构
[1] Univ Turku, Dept Math, FI-20014 Turku, Finland
基金
芬兰科学院;
关键词
cellular automata; undecidability; tiling problem; APERIODIC SET; LIMIT-SETS; ENTROPY; REVERSIBILITY; SENSITIVITY;
D O I
10.1080/03081079.2012.695895
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We survey results on decidability questions concerning cellular automata. Properties discussed include reversibility and surjectivity and their variants, time-symmetry and conservation laws, nilpotency and other properties of the limit set and the trace, properties chaoticity related such as sensitivity to initial conditions and mixing of the space, and dynamics from finite initial configurations. We also discuss briefly the tiling problem and its variants, and consider the influence of the dimension of the space on the decidability status of the questions.
引用
收藏
页码:539 / 554
页数:16
相关论文
共 48 条
  • [1] Amoroso S., 1972, Journal of Computer and System Sciences, V6, P448, DOI 10.1016/S0022-0000(72)80013-8
  • [2] [Anonymous], 1962, P 14 S APPL MATH
  • [3] Berger R., 1966, MEMOIRS AM MATH SOC, V66
  • [4] Ergodicity, transitivity, and regularity for linear cellular automata over Zm
    Cattaneo, G
    Formenti, E
    Manzini, G
    Margara, L
    [J]. THEORETICAL COMPUTER SCIENCE, 2000, 233 (1-2) : 147 - 164
  • [5] ULTIMATE TRACES OF CELLULAR AUTOMATA
    Cervelle, Julien
    Formenti, Enrico
    Guillon, Pierre
    [J]. 27TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2010), 2010, 5 : 155 - 166
  • [6] Transitive cellular automata are sensitive
    Codenotti, B
    Margara, L
    [J]. AMERICAN MATHEMATICAL MONTHLY, 1996, 103 (01) : 58 - 62
  • [7] ON THE LIMIT-SETS OF CELLULAR AUTOMATA
    CULIK, K
    PACHL, J
    YU, S
    [J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (04) : 831 - 842
  • [8] An aperiodic set of 13 Wang tiles
    Culik, K
    [J]. DISCRETE MATHEMATICS, 1996, 160 (1-3) : 245 - 251
  • [9] Culik Karel., 1988, Complex Systems, V2, P177
  • [10] On computing the entropy of cellular automata
    D'amico, M
    Manzini, G
    Margara, L
    [J]. THEORETICAL COMPUTER SCIENCE, 2003, 290 (03) : 1629 - 1646