Index set (recursion theory)
- Index set (recursion theory)
In the field of recursion theory, index sets describe classes of partial recursive functions, specifically they give all indices of functions in that class according to a fixed enumeration of partial recursive functions (a Gödel numbering).
Definition
Fix an enumeration of all partial recursive functions, or equivalently of recursively enumerable sets whereby the "e"th such set is W_{e} and the "e"th such function (whose domain is W_{e}) is phi_{e}.
Let mathcal{A} be a class of partial recursive functions. If A = {x : phi_{x} in mathcal{A} } then A is the index set of mathcal{A}.
Index sets and Rice's theorem
Most index sets are incomputable (non-recursive) aside from two trivial exceptions. This is stated in Rice's theorem:
Let mathcal{C} be a class of partial recursive functions with index set C. Then C is recursive if and only if C is empty, or C is all of omega.
where omega is the set of natural numbers, including zero.
Rice's theorem says "any nontrivial property of partial recursive functions is undecidable"[cite book | title=Classical Recursion Theory, Volume 1| author=Odifreddi, P. G. ; page 151] ]
Notes
References
*cite book | title=Classical Recursion Theory, Volume 1| author=Odifreddi, P. G. | publisher=Elsevier| year=1992 | isbn=0-444-89483-7 | pages=668
* cite book | title=Theory of Recursive Functions and Effective Computability | author=Rogers Jr., Hartley | publisher=MIT Press|isbn=0-262-68052-1 | pages=482 | year=1987
Wikimedia Foundation.
2010.
Look at other dictionaries:
Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… … Wikipedia
Recursion — Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self… … Wikipedia
Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects … Wikipedia
Set (mathematics) — This article gives an introduction to what mathematicians call intuitive or naive set theory; for a more detailed account see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory. The intersection of two sets is… … Wikipedia
Theory (mathematical logic) — This article is about theories in a formal language, as studied in mathematical logic. For other uses, see Theory (disambiguation). In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. Usually… … Wikipedia
Recursion (computer science) — Recursion in computer science is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. [cite book last = Epp first = Susanna title = Discrete Mathematics with Applications year=1995… … Wikipedia
Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown … Wikipedia
Recursively enumerable set — In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing recognizable if: There is an algorithm such that the set of… … 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
Intuitionistic type theory — Intuitionistic type theory, or constructive type theory, or Martin Löf type theory or just Type Theory is a logical system and a set theory based on the principles of mathematical constructivism. Intuitionistic type theory was introduced by Per… … Wikipedia