In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals \alpha. An admissible set is closed under functions, where L_\xi denotes a rank of Godel's constructible hierarchy. \alpha is an admissible ordinal if L_{\alpha} is a model of Kripke–Platek set theory. In what follows \alpha is considered to be fixed.

Definitions

The objects of study in \alpha recursion are subsets of \alpha. These sets are said to have some properties: There are also some similar definitions for functions mapping \alpha to \alpha: Additional connections between recursion theory and α recursion theory can be drawn, although explicit definitions may not have yet been written to formalize them: We say R is a reduction procedure if it is \alpha recursively enumerable and every member of R is of the form where H, J, K are all α-finite. A is said to be α-recursive in B if there exist R_0,R_1 reduction procedures such that: If A is recursive in B this is written. By this definition A is recursive in (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being. We say A is regular if or in other words if every initial portion of A is α-finite.

Work in α recursion

Shore's splitting theorem: Let A be \alpha recursively enumerable and regular. There exist \alpha recursively enumerable B_0,B_1 such that Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that then there exists a regular α-recursively enumerable set B such that. Barwise has proved that the sets \Sigma_1-definable on are exactly the sets \Pi_1^1-definable on L_\alpha, where \alpha^+ denotes the next admissible ordinal above \alpha, and \Sigma is from the Levy hierarchy. There is a generalization of limit computability to partial functions. A computational interpretation of \alpha-recursion exists, using "\alpha-Turing machines" with a two-symbol tape of length \alpha, that at limit computation steps take the limit inferior of cell contents, state, and head position. For admissible \alpha, a set is \alpha-recursive iff it is computable by an \alpha-Turing machine, and A is \alpha-recursively-enumerable iff A is the range of a function computable by an \alpha-Turing machine. A problem in α-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible \alpha, the automorphisms of the \alpha-enumeration degrees embed into the automorphisms of the \alpha-enumeration degrees.

Relationship to analysis

Some results in \alpha-recursion can be translated into similar results about second-order arithmetic. This is because of the relationship L has with the ramified analytic hierarchy, an analog of L for the language of second-order arithmetic, that consists of sets of integers. In fact, when dealing with first-order logic only, the correspondence can be close enough that for some results on, the arithmetical and Levy hierarchies can become interchangeable. For example, a set of natural numbers is definable by a \Sigma_1^0 formula iff it's \Sigma_1-definable on L_\omega, where \Sigma_1 is a level of the Levy hierarchy. More generally, definability of a subset of ω over HF with a \Sigma_n formula coincides with its arithmetical definability using a \Sigma_n^0 formula.

Inline references