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(L_alpha) 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:

: K subseteq A leftrightarrow exists H: exists J: [ in R_0 wedge H subseteq B wedge J subseteq alpha / B ] ,

: K subseteq alpha / A leftrightarrow exists H: exists J: [ in R_1 wedge H subseteq B wedge J subseteq alpha / B ] .

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(L_alpha [B] ).

We say "A" is regular if forall eta in alpha: A cap eta in L_alpha 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 (i<2).

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