Cellular automata and intermediate degrees

摘要

We study a classification of cellular automata based on the Turing degree of the orbits of the automaton. The difficulty of determining the membership of a cellular automaton in any one of these classes is characterized in the arithmetical hierarchy. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 14]