RICE THEOREM FOR THE LIMIT-SETS OF CELLULAR-AUTOMATA

Authors
KARI J
Citation
J. Kari, RICE THEOREM FOR THE LIMIT-SETS OF CELLULAR-AUTOMATA, Theoretical computer science, 127(2), 1994, pp. 229-254
Citations number
7
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
127
Issue
2
Year of publication
1994
Pages
229 - 254
Database
ISI
SICI code
0304-3975(1994)127:2<229:RTFTLO>2.0.ZU;2-U
Abstract
Rice's theorem is a well-known result in the theory of recursive funct ions, A corresponding theorem for cellular automata limit sets is prov ed: All nontrivial properties of limit sets of cellular automata (CAs) are shown undecidable. The theorem remains valid even if only one-dim ensional CAs are considered.