Definitions

# 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 eth such set is $W_\left\{e\right\}$ and the eth such function (whose domain is $W_\left\{e\right\}$) is $phi_\left\{e\right\}$.

Let $mathcal\left\{A\right\}$ be a class of partial recursive functions. If $A = \left\{x : phi_\left\{x\right\} in mathcal\left\{A\right\} \right\}$ then $A$ is the index set of $mathcal\left\{A\right\}$.

## 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\left\{C\right\}$ 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"

## References

Search another word or see Index setson Dictionary | Thesaurus |Spanish