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 条
[41]  
Myhill J., 1963, Proc. Am. Math. Soc, V14, P685, DOI DOI 10.2307/2034301.
[42]   UNDECIDABILITY AND NONPERIODICITY FOR TILINGS OF PLANE [J].
ROBINSON, RM .
INVENTIONES MATHEMATICAE, 1971, 12 (03) :177-&
[43]  
Salo V., CORR
[44]   EXPANSIVENESS, ENTROPY AND POLYNOMIAL-GROWTH FOR GROUPS ACTING ON SUBSHIFTS BY AUTOMORPHISMS [J].
SHERESHEVSKY, MA .
INDAGATIONES MATHEMATICAE-NEW SERIES, 1993, 4 (02) :203-210
[45]  
Sutner K., 1989, Complex Systems, V3, P107
[46]  
Sutner K., 1991, Complex Systems, V5, P19
[47]  
Turing AM, 1937, P LOND MATH SOC, V42, P230, DOI 10.1112/plms/s2-42.1.230
[48]   PROVING THEOREMS BY PATTERN RECOGNITION .1. [J].
WANG, H .
COMMUNICATIONS OF THE ACM, 1960, 3 (04) :220-234
12345