In recursion theory
, the mathematical theory of computability, alpha recursion
(often written α recursion
) is a generalisation of recursion theory
to subsets of admissible ordinals
. An admissible ordinal is closed under
functions. Admissible ordinals are models of Kripke–Platek set theory
. In what follows
is considered to be fixed.
The objects of study in recursion are subsets of . A is said to be recursively enumerable if it is definable over . A is recursive if both A and (its complement in ) are recursively enumerable.
Members of are called finite and play a similar role to the finite numbers in classical recursion theory.
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 α-recusive 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 it should be noted that 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.
Results in recursion
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 .
- Gerald Sacks, Higher recursion theory, Springer Verlag, 1990
- Robert Soare, Recursively Enumerable Sets and Degrees, Springer Verlag, 1987