Priority arguments in transfinite computability theory
Steef Hegeman
Abstract:
The priority method has been used to examine the structure of the semi-decidable degrees in computability theory. We discuss three classical results (the Friedberg-Muchnik theorem, the splitting theorem, and the thickness lemma) and discuss whether their proofs could be adapted to transfinite computability theory, specifically to the machine models of ITTMs, α-machines, and p-α-machines (α-machines equipped an extra ordinal parameter). We prove a splitting theorem for certain ITTM-semi-decidable sets—sufficient to conclude that there are infinitely many ITTM-semi-decidable degrees—and a thickness lemma for certain ITTM-semi-decidable sets of low degree. We sketch results for α-machines and p-OTMs (ordinal Turing machines with an extra parameter), among which a splitting theorem and a thickness lemma for p-OTMs.