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

Let $\varphi _{e}$ be a computable enumeration of all partial computable functions, and $W_{e}$ be a computable enumeration of all c.e. sets.

Let ${\mathcal {A}}$ be a class of partial computable functions. If $A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}$ then $A$ is the index set of ${\mathcal {A}}$ . In general $A$ is an index set if for every $x,y\in \mathbb {N}$ 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 {C}}$ 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 {N}$ .

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

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:^[2]

$\mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}$ is $\Pi _{1}$ -complete.
$\mathrm {Fin} =\{e\,:\,W_{e}{\text{ is finite}}\}$ is $\Sigma _{2}$ -complete.
$\mathrm {Inf} =\{e\,:\,W_{e}{\text{ is infinite}}\}$ is $\Pi _{2}$ -complete.
$\mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}$ is $\Pi _{2}$ -complete.
$\mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ is total and constant}}\}$ is $\Pi _{2}$ -complete.
$\mathrm {Cof} =\{e\,:\,W_{e}{\text{ is cofinite}}\}$ is $\Sigma _{3}$ -complete.
$\mathrm {Rec} =\{e\,:\,W_{e}{\text{ is computable}}\}$ is $\Sigma _{3}$ -complete.
$\mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ is extendible to a total computable function}}\}$ is $\Sigma _{3}$ -complete.
$\mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}$ is $\Sigma _{4}$ -complete, where $\mathrm {HP}$ is the halting problem.

Empirically, if the "most obvious" definition of a set $A$ is $\Sigma _{n}$ [resp. $\Pi _{n}$ ], we can usually show that $A$ is $\Sigma _{n}$ -complete [resp. $\Pi _{n}$ -complete].

Notes

^ Odifreddi, P. G. Classical Recursion Theory, Volume 1.; page 151
^ 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

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.

[odifreddi-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

[1]

[2]