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).
Contents
Definition
Fix an enumeration of all partial recursive functions, or equivalently of recursively enumerable sets whereby the eth such set is
Let
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
where
Rice's theorem says "any nontrivial property of partial recursive functions is undecidable"