Alpha recursion theory: Difference between revisions

Revision as of 02:46, 3 July 2007

Revision as of 02:47, 3 July 2007

Line 1:

In [[recursion theory]], the mathematical theory of computability, '''Alphaalpha recursion''' (often written '''&alpha; recursion''') 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 it is <math> \Sigma_1</math> definable over <math>L_\alpha</math>. A is recursive if both A is recursively enumerable and <math>\alpha / A</math> is recursively enumerable.