Cellular Automata and Intermediate Degrees
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.
(April 20, 2004)