Alpha recursion theory: Difference between revisions

Revision as of 23:43, 3 June 2008

Revision as of 22:58, 15 June 2008

Line 1:

In [[recursion theory]], the mathematical theory of computability, '''alpha recursion''' (often written '''α 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 and <math>\alpha / A</math> (its complement in <math>\alpha</math>) are 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.