Classes of partial recursive functions
In computability theory, index sets describe classes of computable functions; specifically, they give all indices of functions in a certain class, according to a fixed Gödel numbering of partial computable functions.
Definition.
Let formula_1 be a computable enumeration of all partial computable functions, and formula_2 be a computable enumeration of all c.e. sets.
Let formula_3 be a class of partial computable functions. If formula_4 then formula_5 is the index set of formula_3. In general formula_5 is an index set if for every formula_8 with formula_9 (i.e. they index the same function), we have formula_10. 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 non-computable, aside from two trivial exceptions. This is stated in Rice's theorem:
Let formula_11 be a class of partial computable functions with its index set formula_12. Then formula_12 is computable if and only if formula_12 is empty, or formula_12 is all of formula_16.
Rice's theorem says "any nontrivial property of partial computable functions is undecidable".
Completeness in the arithmetical hierarchy.
Index sets provide many examples of sets which are complete at some level of the arithmetical hierarchy. Here, we say a formula_17 set formula_5 is "formula_17-complete" if, for every formula_17 set formula_21, there is an m-reduction from formula_21 to formula_5. formula_24-completeness is defined similarly. Here are some examples:
Empirically, if the "most obvious" definition of a set formula_5 is formula_17 [resp. formula_24], we can usually show that formula_5 is formula_17-complete [resp. formula_24-complete].
Notes.
 ;templatestyles src="Reflist/styles.css" / ;