Ordinal Machines and Admissible Recursion Theory

We generalize standard Turing machines working in time ω on a tape of length ω to abstract machines with time α and tape length α, for α some limit ordinal. This model of computation determines an associated computability theory: α-computability theory. We compare the new theory to α-recursion theory, which was developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-computable and α-recursive as well as α-computably enumerable and α-recursively enumerable completely agree. Moreover there is an isomorphism of parts of the degree structure induced by α-computability and of a degree structure in α-recursion theory, which allows us to transfer, e.g., the Sacks-Simpson theorem or Shore’s density theorem to α-computability theory. We emphasize the algorithmic approach by giving a proof of the Sacks-Simpson theorem, which is solely based on α-machines and does not rely on constructibility theory