A Note on Culik-Yu Classes
Klaus Sutner · Complex Systems · 1989
Culik and Yu suggested a classification of cellular a u tomata into four classes based on Wolfram's earlier heuristic classifi cation. The purpose of this note is to determine the position of these classes within th e arithmetical hierarchy. We will show t hat CLASS ONE and C LASS T wo are rrg-complete whereas C LASS THREE is ~g complete . C LASS FOUR is tri vial.