A Note on Culik-Yu Classes
Klaus Sutner
Stevens Institute of Technology, Hoboken, NJ 07030, USA
Abstract
Culik and Yu suggested a classification of cellular automata into four classes based on Wolfram's earlier heuristic classification. The purpose of this note is to determine the position of these classes within the arithmetical hierarchy. We will show that Class One and Class Two are 
-complete whereas Class Three is 
-complete. Class Four is trivial.
