Index set (computability)

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

edit

Let   be a computable enumeration of all partial computable functions, and   be a computable enumeration of all c.e. sets.

Let   be a class of partial computable functions. If   then   is the index set of  . In general   is an index set if for every   with   (i.e. they index the same function), we have  . 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

edit

Most index sets are non-computable, aside from two trivial exceptions. This is stated in Rice's theorem:

Let   be a class of partial computable functions with its index set  . Then   is computable if and only if   is empty, or   is all of  .

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

Completeness in the arithmetical hierarchy

edit

Index sets provide many examples of sets which are complete at some level of the arithmetical hierarchy. Here, we say a   set   is  -complete if, for every   set  , there is an m-reduction from   to  .  -completeness is defined similarly. Here are some examples:[2]

  •   is  -complete.
  •   is  -complete.
  •   is  -complete.
  •   is  -complete.
  •   is  -complete.
  •   is  -complete.
  •   is  -complete.
  •   is  -complete.
  •   is  -complete, where   is the halting problem.

Empirically, if the "most obvious" definition of a set   is   [resp.  ], we can usually show that   is  -complete [resp.  -complete].

Notes

edit
  1. ^ Odifreddi, P. G. Classical Recursion Theory, Volume 1.; page 151
  2. ^ Soare, Robert I. (2016), "Turing Reducibility", Turing Computability, Theory and Applications of Computability, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 51–78, doi:10.1007/978-3-642-31933-4_3, ISBN 978-3-642-31932-7, retrieved 2021-04-21

References

edit
  • 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.