Computation with Infinite Programs
Ethan S. Lewis

Abstract:
Koepke introduced a machine model of computation that uses infinite time and space. In our thesis, we generalize Koepke’s model by allowing for infinite programs in addition to infinite time and space. With this new model of computation, we prove generalizations of basic results from finite computability theory. Furthermore, we introduce the axiom of computable enumerability and show that it is independent of Gödel-Bernays class theory with the axiom of global choice. Assuming this axiom, we prove results that characterize the computably enumerable and decidable classes, as well as the computable functions.