In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals . An admissible set is closed under functions, where denotes a rank of Godel's constructible hierarchy. is an admissible ordinal if is a model of Kripke–Platek set theory. In what follows is considered to be fixed.
The objects of study in recursion are subsets of . These sets are said to have some properties:
There are also some similar definitions for functions mapping to : [3]
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 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 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.
Shore's splitting theorem: Let A be recursively enumerable and regular. There exist recursively enumerable 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 -definable on are exactly the sets -definable on , where denotes the next admissible ordinal above , and is from the Levy hierarchy. [5]
There is a generalization of limit computability to partial functions. [6]
A computational interpretation of -recursion exists, using "-Turing machines" with a two-symbol tape of length , that at limit computation steps take the limit inferior of cell contents, state, and head position. For admissible , a set is -recursive iff it is computable by an -Turing machine, and is -recursively-enumerable iff is the range of a function computable by an -Turing machine. [7]
A problem in α-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible , the automorphisms of the -enumeration degrees embed into the automorphisms of the -enumeration degrees. [8]
Some results in -recursion can be translated into similar results about second-order arithmetic. This is because of the relationship has with the ramified analytic hierarchy, an analog of for the language of second-order arithmetic, that consists of sets of integers. [9]
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 formula iff it's -definable on , where is a level of the Levy hierarchy. [10] More generally, definability of a subset of ω over HF with a formula coincides with its arithmetical definability using a formula. [11]
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals . An admissible set is closed under functions, where denotes a rank of Godel's constructible hierarchy. is an admissible ordinal if is a model of Kripke–Platek set theory. In what follows is considered to be fixed.
The objects of study in recursion are subsets of . These sets are said to have some properties:
There are also some similar definitions for functions mapping to : [3]
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 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 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.
Shore's splitting theorem: Let A be recursively enumerable and regular. There exist recursively enumerable 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 -definable on are exactly the sets -definable on , where denotes the next admissible ordinal above , and is from the Levy hierarchy. [5]
There is a generalization of limit computability to partial functions. [6]
A computational interpretation of -recursion exists, using "-Turing machines" with a two-symbol tape of length , that at limit computation steps take the limit inferior of cell contents, state, and head position. For admissible , a set is -recursive iff it is computable by an -Turing machine, and is -recursively-enumerable iff is the range of a function computable by an -Turing machine. [7]
A problem in α-recursion theory which is open (as of 2019) is the embedding conjecture for admissible ordinals, which is whether for all admissible , the automorphisms of the -enumeration degrees embed into the automorphisms of the -enumeration degrees. [8]
Some results in -recursion can be translated into similar results about second-order arithmetic. This is because of the relationship has with the ramified analytic hierarchy, an analog of for the language of second-order arithmetic, that consists of sets of integers. [9]
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 formula iff it's -definable on , where is a level of the Levy hierarchy. [10] More generally, definability of a subset of ω over HF with a formula coincides with its arithmetical definability using a formula. [11]