- Alpha recursion theory
recursion theory, the mathematical theory of computability, alpha recursion (often written α recursion) is a generalisation of recursion theoryto subsets of admissible ordinals . An admissible ordinal is closed under functions. Admissible ordinals are models of Kripke–Platek set theory. In what follows is considered to be fixed.
The objects of study in recursion are subsets of . A is said to be recursively enumerable if it is definable over . A is recursive if both A and (its complement in ) are recursively enumerable.
Members of are called 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 where "H", "J", "K" are all α-finite.
"A" is said to be α-recusive in "B" if there exist reduction procedures such that:
If "A" is recursive in "B" this is written . By this definition "A" is recursive in (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 .
We say "A" is regular if or in other words if every initial portion of "A" is α-finite.
Results in recursion
Shore's splitting theorem: Let A be recursively enumerable and regular. There exist recursively enumerable such that
Shore's density theorem: Let "A", "C" be α-regular recursively enumerable sets such that then there exists a regular α-recursively enumerable set "B" such that .
* 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