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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.