THE SURJECTIVITY PROBLEM FOR 2D CELLULAR-AUTOMATA

被引：15
作者：
DURAND, B
机构：
[1] Laboratoire de l’Informatique du Parallélisme, ENS-Lyon, 69364 Lyon 07
来源：
JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1994年 / 49卷 / 03期
关键词：
D O I：
10.1016/S0022-0000(05)80077-7
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The surjectivity problem for 2D cellular automata was proved undecidable in 1989 by Jarkko Kari. The proof consists in a reduction of a problem concerning finite tilings into the previous one. This reduction uses a special and very sophisticated tile set. In this article, we present a much more simple tile set which can play the same role. (C) 1994 Academic Press, Inc.
引用
收藏
页码：718 / 725
页数：8
相关论文
共 14 条
[1]  
Amoroso S., 1972, Journal of Computer and System Sciences, V6, P448, DOI 10.1016/S0022-0000(72)80013-8
[2]  
Berger R., 1966, MEM AM MATH SOC, V66
[3]   ON THE LIMIT-SETS OF CELLULAR AUTOMATA [J].
CULIK, K ;
PACHL, J ;
YU, S .
SIAM JOURNAL ON COMPUTING, 1989, 18 (04) :831-842
[4]   REVERSIBILITY OF 2D CELLULAR AUTOMATA IS UNDECIDABLE [J].
KARI, J .
PHYSICA D, 1990, 45 (1-3) :379-385
[5]  
KARI J, 1994, J COMPUT SYSTEM SCI, V48
[6]  
Moore Edward Forrest, 1962, P S APPL MATH, V14, P13
[7]  
MORITA K, 1990, T IEICE E, P987
[8]  
MORITA K, 1992, IEICE T INF SYST, P141
[9]  
MYHILL J, 1963, P AM MATH SOC, V14, P485
[10]  
Richardson D., 1972, Journal of Computer and System Sciences, V6, P373, DOI 10.1016/S0022-0000(72)80009-6
12