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 $\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}$. 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 $\omega$.

where $\omega$ is the set of natural numbers, including zero.

Rice's theorem says "any nontrivial property of partial recursive functions is undecidable"^[1]

Notes

1. Odifreddi, P. G. Classical Recursion Theory, Volume 1.; page 151

References

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