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 ${\displaystyle W_{e}}$ and the eth such function (whose domain is ${\displaystyle W_{e}}$) is ${\displaystyle \phi _{e}}$.

Let ${\mathcal {A}}$ be a class of partial recursive functions. If ${\displaystyle 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 ${\displaystyle x,y\in \mathbb {N} }$ with ${\displaystyle \phi _{x}\simeq \phi _{y}}$ (i.e. they index the same function), we have ${\displaystyle 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.