RICE THEOREM FOR THE LIMIT-SETS OF CELLULAR-AUTOMATA

被引：65

作者：

KARI, J

机构：

[1] Mathematics Department, University of Turku

来源：

THEORETICAL COMPUTER SCIENCE | 1994年 / 127卷 / 02期

关键词：

Cellular arrays - Function evaluation;

D O I：

10.1016/0304-3975(94)90041-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Rice's theorem is a well-known result in the theory of recursive functions, A corresponding theorem for cellular automata limit sets is proved: All nontrivial properties of limit sets of cellular automata (CAs) are shown undecidable. The theorem remains valid even if only one-dimensional CAs are considered.

引用

页码：229 / 254

页数：26

共 7 条

[1] Amoroso S., 1972, Journal of Computer and System Sciences, V6, P448, DOI 10.1016/S0022-0000(72)80013-8
[2] FORMAL LANGUAGES AND GLOBAL CELLULAR AUTOMATON BEHAVIOR
CULIK, K
HURD, LP
YU, S
[J]. PHYSICA D, 1990, 45 (1-3): : 396 - 403
[3] ON THE LIMIT-SETS OF CELLULAR AUTOMATA
CULIK, K
PACHL, J
YU, S
[J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (04) : 831 - 842
[4] Hurd L. P., 1987, Complex Systems, V1, P69
[5] THE NILPOTENCY PROBLEM OF ONE-DIMENSIONAL CELLULAR AUTOMATA
KARI, J
[J]. SIAM JOURNAL ON COMPUTING, 1992, 21 (03) : 571 - 586
[6] Moore EF, 1964, SEQUENTIAL MACHINES
[7] Salomaa A., 1985, COMPUTATION AUTOMATA

← 1 →