Content deleted Content added
m Robot - Moving category Recursion theory to Computability theory per CFD at Wikipedia:Categories for discussion/Log/2011 February 5. |
In definition of alpha-recursivity, made use of *alpha*-r.e. explicit. Hope this avoids possible confusion. |
||
Line 1:
In [[recursion theory]], '''α recursion theory''' is a generalisation of [[recursion theory]] to subsets of [[admissible ordinal]]s <math>\alpha</math>. An admissible ordinal is closed under <math>\Sigma_1(L_\alpha)</math> functions. Admissible ordinals are models of [[Kripke–Platek set theory]]. In what follows <math>\alpha</math> is considered to be fixed.
The objects of study in <math>\alpha</math> recursion are subsets of <math>\alpha</math>. A is said to be '''<math>\alpha</math> recursively enumerable''' if it is <math> \Sigma_1</math> definable over <math>L_\alpha</math>. A is recursive if both A and <math>\alpha / A</math> (its complement in <math>\alpha</math>) are <math>\alpha</math> recursively enumerable.
Members of <math>L_\alpha</math> are called <math>\alpha</math> finite and play a similar role to the finite numbers in classical recursion theory.
| |||