In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals <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>.

PropertyValue
dbpprop:abstract
  • In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals <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 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. We say R is a reduction procedure if it is recursively enumerable and every member of R is of the form <math> \langle H,J,K\rangle </math> where H, J, K are all α-finite. A is said to be α-recusive in B if there exist <math>R_0,R_1</math> reduction procedures such that: <math>K \subseteq A \leftrightarrow \exists H: \exists J:[<H,J,K> \in R_0 \wedge H \subseteq B \wedge J \subseteq \alpha / B ],</math> <math>K \subseteq \alpha / A \leftrightarrow \exists H: \exists J:[<H,J,K> \in R_1 \wedge H \subseteq B \wedge J \subseteq \alpha / B ]. </math> If A is recursive in B this is written <math>\scriptstyle A \le_\alpha B</math>. By this definition A is recursive in <math>\scriptstyle\varnothing</math> if and only if A is recursive. However it should be noted that A being recursive in B is not equivalent to A being <math>\Sigma_1(L_\alpha)</math>. We say A is regular if <math>\forall \beta \in \alpha: A \cap \beta \in L_\alpha</math> or in other words if every initial portion of A is α-finite.
dbpprop:hasPhotoCollection
rdfs:comment
  • In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals <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>.
rdfs:label
  • Alpha recursion theory
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of