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