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 [math]\displaystyle{ W_{e} }[/math] and the eth such function (whose domain is [math]\displaystyle{ W_{e} }[/math]) is [math]\displaystyle{ \phi_{e} }[/math].

Let [math]\displaystyle{ \mathcal{A} }[/math] be a class of partial recursive functions. If [math]\displaystyle{ A = \{x : \phi_{x} \in \mathcal{A} \} }[/math] then [math]\displaystyle{ A }[/math] is the index set of [math]\displaystyle{ \mathcal{A} }[/math]. In general [math]\displaystyle{ A }[/math] is an index set if for every [math]\displaystyle{ x,y \in \mathbb{N} }[/math] with [math]\displaystyle{ \phi_x \simeq \phi_y }[/math] (i.e. they index the same function), we have [math]\displaystyle{ x \in A \leftrightarrow y \in A }[/math]. 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 [math]\displaystyle{ \mathcal{C} }[/math] be a class of partial recursive functions with index set [math]\displaystyle{ C }[/math]. Then [math]\displaystyle{ C }[/math] is recursive if and only if [math]\displaystyle{ C }[/math] is empty, or [math]\displaystyle{ C }[/math] is all of [math]\displaystyle{ \omega }[/math].

where [math]\displaystyle{ \omega }[/math] is the set of natural numbers, including zero.

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

Notes

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. 

0.00 (0 votes)