Towards a Rice Theorem on Traces of Cellular Automata

Julien Cervelle (1) , Pierre Guillon (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram. We prove the undecidability of a rather large class of problems over trace subshifts of cellular automata.

Domaines: Algorithme et structure de données [cs.DS]

Julien Cervelle, Pierre Guillon. Towards a Rice Theorem on Traces of Cellular Automata. 32th International Symposium on Mathematical Foundations of Computer Science (MFCS'07), Aug 2007, Český Krumlov, Czech Republic, Czech Republic. pp.310-319. ⟨hal-00620284⟩