Definitions
Nearby Words

# Alpha recursion theory

In recursion theory, the mathematical theory of computability, alpha recursion (often written α recursion) is a generalisation of recursion theory to subsets of admissible ordinals $alpha$. An admissible ordinal is closed under $Sigma_1\left(L_alpha\right)$ functions. Admissible ordinals are models of Kripke–Platek set theory. In what follows $alpha$ is considered to be fixed.

The objects of study in $alpha$ recursion are subsets of $alpha$. A is said to be $alpha$ recursively enumerable if it is $Sigma_1$ definable over $L_alpha$. A is recursive if both A and $alpha / A$ (its complement in $alpha$) are recursively enumerable.

Members of $L_alpha$ are called $alpha$ 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 $langle H,J,Krangle$ where H, J, K are all α-finite.

A is said to be α-recusive in B if there exist $R_0,R_1$ reduction procedures such that:

If A is recursive in B this is written $scriptstyle A le_alpha B$. By this definition A is recursive in $scriptstylevarnothing$ (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 $Sigma_1\left(L_alpha\left[B\right]\right)$.

We say A is regular if $forall beta in alpha: A cap beta in L_alpha$ or in other words if every initial portion of A is α-finite.

## Results in $alpha$ recursion

Shore's splitting theorem: Let A be $alpha$ recursively enumerable and regular. There exist $alpha$ recursively enumerable $B_0,B_1$ such that $A=B_0 cup B_1 wedge B_0 cap B_1 = varnothing wedge A notle_alpha B_i \left(i<2\right).$

Shore's density theorem: Let A, C be α-regular recursively enumerable sets such that $scriptstyle A <_alpha C$ then there exists a regular α-recursively enumerable set B such that $scriptstyle A <_alpha B <_alpha C$.

## References

• Gerald Sacks, Higher recursion theory, Springer Verlag, 1990
• Robert Soare, Recursively Enumerable Sets and Degrees, Springer Verlag, 1987

Search another word or see Alpha recursionon Dictionary | Thesaurus |Spanish