Index Set (recursion Theory)

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 $\varphi_e$ be a computable enumeration of all partial computable functions, and $W_$ be a computable enumeration of all c.e. sets.

Let $\mathcal$ be a class of partial computable functions. If $A = \$ then $A$ is the index set of $\mathcal$. In general $A$ is an index set if for every $x,y \in \mathbb$ with $\varphi_x \simeq \varphi_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 non-computable, aside from two trivial exceptions. This is stated in Rice's theorem:

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

Rice's theorem says "any nontrivial property of partial computable functions is undecidable".; page 151

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 $\Sigma_n$ set $A$ is ''$\Sigma_n$-complete'' if, for every $\Sigma_n$ set $B$, there is an m-reduction from $B$ to $A$. $\Pi_n$-completeness is defined similarly. Here are some examples:

* $\mathrm = \$ is $\Pi_1$-complete.
* $\mathrm = \$ is $\Sigma_2$-complete.
* $\mathrm = \$ is $\Pi_2$-complete.
* $\mathrm = \ = \$ is $\Pi_2$-complete.
* $\mathrm = \$ is $\Pi_2$-complete.
* $\mathrm = \$ is $\Sigma_3$-complete.
* $\mathrm = \$ is $\Sigma_3$-complete.
* $\mathrm = \$ is $\Sigma_3$-complete.
* $\mathrm = \$ is $\Sigma_4$-complete, where $\mathrm$ is the halting problem.

Empirically, if the "most obvious" definition of a set $A$ is $\Sigma_n$ esp. $\Pi_n$ we can usually show that $A$ is $\Sigma_n$-complete esp. $\Pi_n$-complete

Notes

References

*
*{{ cite book , title=Theory of Recursive Functions and Effective Computability , author=Rogers Jr., Hartley , publisher=MIT Press, isbn=0-262-68052-1 , pages=482 , year=1987

Computability theory