Decidability and undecidability in cellular automata

被引：8
作者：
Kari, Jarkko [1 ]
机构：
[1] Univ Turku, Dept Math, FI-20014 Turku, Finland
来源：
INTERNATIONAL JOURNAL OF GENERAL SYSTEMS | 2012年 / 41卷 / 06期
基金：
芬兰科学院;
关键词：
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 条
[11]   Number-conserving cellular automata I:: decidability [J].
Durand, B ;
Formenti, E ;
Róka, Z .
THEORETICAL COMPUTER SCIENCE, 2003, 299 (1-3) :523-535
[12]   THE SURJECTIVITY PROBLEM FOR 2D CELLULAR-AUTOMATA [J].
DURAND, B .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 49 (03) :718-725
[13]  
Durand B., 2009, CORR
[14]  
Durand B., 2003, Discrete Models for Complex Systems, DMCS'03, volume AB of DMTCS Proceedings, P117
[15]   Lyapunov exponents versus expansivity and sensitivity in cellular automata [J].
Finelli, M ;
Manzini, G ;
Margara, L .
JOURNAL OF COMPLEXITY, 1998, 14 (02) :210-233
[16]   On the hierarchy of conservation laws in a cellular automaton [J].
Formenti, Enrico ;
Kari, Jarkko ;
Taati, Siamak .
NATURAL COMPUTING, 2011, 10 (04) :1275-1294
[17]   On time-symmetry in cellular automata [J].
Gajardo, Anahi ;
Kari, Jarkko ;
Moreira, Andres .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2012, 78 (04) :1115-1126
[18]   REVISITING THE RICE THEOREM OF CELLULAR AUTOMATA [J].
Guillon, Pierre ;
Richard, Gaetan .
27TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2010), 2010, 5 :441-451
[19]  
Gurevich Yuri, 1972, SIBERIAN MATH J, V13, P319, DOI DOI 10.1007/BF00971620
[20]   ADDITIVE CONSERVED QUANTITIES IN DISCRETE-TIME LATTICE DYNAMIC-SYSTEMS [J].
HATTORI, T ;
TAKESUE, S .
PHYSICA D, 1991, 49 (03) :295-322
12345