Complex Systems

A Note on Culik-Yu Classes Download PDF

Klaus Sutner
Stevens Institute of Technology, Hoboken, NJ 07030, USA


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.