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_e and the eth such function (whose domain is W_e) is ϕ_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}$. In general A is an index set if for every $x,y \in \mathbb{N}$ with $\phi_x \simeq \phi_y$ (i.e. they index the same function), we have $x \in A \leftrightarrow y \in A$. Intuitively, these are the sets of natural numbers that we describe only with reference to the functions they index.

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 ω.

where ω is the set of natural numbers, including zero.

Rice's theorem says "any nontrivial property of partial recursive functions is undecidable"

References

• Odifreddi, P. G. (1992). Classical Recursion Theory, Volume 1. Elsevier. pp. 668. ISBN 0-444-89483-7. 
• Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. pp. 482. ISBN 0-262-68052-1.