In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals
An admissible set is closed under
denotes a rank of Godel's constructible hierarchy.
is a model of Kripke–Platek set theory.
These sets are said to have some properties: There are also some similar definitions for functions mapping
:[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
reduction procedures such that: If A is recursive in B this is written
or in other words if every initial portion of A is α-finite.
Shore's splitting theorem: Let A be
recursively enumerable and regular.
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
denotes the next admissible ordinal above
[5] There is a generalization of limit computability to partial
-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.
is the range of a function computable by an
[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
-enumeration degrees embed into the automorphisms of the
-recursion can be translated into similar results about second-order arithmetic.
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
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