Cellular Automata and Intermediate Degrees

Klaus Sutner
Carnegie Mellon University

The existence of intermediate degrees of computability is one of the central results of twentieth century recursion theory (priority method). We will explore the impact of this result on the study of computational properties of CA and reversible CA and show that the classical results carry over, mutatis mutandis, to the realm of CA.

Created by Mathematica  (April 20, 2004)