# Alpha recursion theory

﻿
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,K angle$ 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 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 otle_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

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Reduction (recursion theory) — In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively… …   Wikipedia

• Hyperarithmetical theory — In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an… …   Wikipedia

• Descriptive set theory — In mathematical logic, descriptive set theory is the study of certain classes of well behaved subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to other… …   Wikipedia

• Left recursion — In computer science, left recursion is a special case of recursion. In terms of context free grammar, a non terminal r is left recursive if the left most symbol in any of r’s ‘alternatives’ either immediately (direct left recursive) or through… …   Wikipedia

• Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

• List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

• Richard A. Shore — Richard Arnold Shore (* 18. August 1946) ist ein US amerikanischer mathematischer Logiker, der sich vor allem mit Rekursionstheorie beschäftigt. Shore promovierte 1972 am Massachusetts Institute of Technology bei Gerald E. Sacks (Priority… …   Deutsch Wikipedia

• Lambda calculus — In mathematical logic and computer science, lambda calculus, also written as λ calculus, is a formal system designed to investigate function definition, function application and recursion. It was introduced by Alonzo Church and Stephen Cole… …   Wikipedia

• Ackermann function — In recursion theory, the Ackermann function or Ackermann Péter function is a simple example of a general recursive function that is not primitive recursive. General recursive functions are also known as computable functions. The set of primitive… …   Wikipedia

• Computability — You might be looking for Computable function, Computability theory, Computation, or Theory of computation. Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within… …   Wikipedia