Index set (computability) (original) (raw)

From Wikipedia, the free encyclopedia

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.

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

Let A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ be a class of partial computable functions. If A = { x : φ x ∈ A } {\displaystyle A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}} $A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}$ then A {\displaystyle A} $A$ is the index set of A {\displaystyle {\mathcal {A}}} ${\mathcal {A}}$ . In general A {\displaystyle A} $A$ is an index set if for every x , y ∈ N {\displaystyle x,y\in \mathbb {N} } $x,y\in \mathbb {N}$ with φ x ≃ φ y {\displaystyle \varphi _{x}\simeq \varphi _{y}} $\varphi _{x}\simeq \varphi _{y}$ (i.e. they index the same function), we have x ∈ A ↔ y ∈ A {\displaystyle x\in A\leftrightarrow y\in A} $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

[edit]

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

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

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 Σ n {\displaystyle \Sigma _{n}} $\Sigma _{n}$ set A {\displaystyle A} $A$ is Σ n {\displaystyle \Sigma _{n}} $\Sigma {n}$ -complete if, for every Σ n {\displaystyle \Sigma _{n}} $\Sigma _{n}$ set B {\displaystyle B} $B$ , there is an m-reduction from B {\displaystyle B} $B$ to A {\displaystyle A} $A$ . Π n {\displaystyle \Pi _{n}} $\Pi _{n}$ -completeness is defined similarly. Here are some examples:[2]

E m p = { e : W e = ∅ } {\displaystyle \mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}} $\mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}$ is Π 1 {\displaystyle \Pi _{1}} $\Pi _{1}$ -complete.
F i n = { e : W e is finite } {\displaystyle \mathrm {Fin} =\{e\,:\,W_{e}{\text{ is finite}}\}} $\mathrm {Fin} =\{e\,:\,W_{e}{\text{ is finite}}\}$ is Σ 2 {\displaystyle \Sigma _{2}} $\Sigma _{2}$ -complete.
I n f = { e : W e is infinite } {\displaystyle \mathrm {Inf} =\{e\,:\,W_{e}{\text{ is infinite}}\}} $\mathrm {Inf} =\{e\,:\,W_{e}{\text{ is infinite}}\}$ is Π 2 {\displaystyle \Pi _{2}} $\Pi _{2}$ -complete.
T o t = { e : φ e is total } = { e : W e = N } {\displaystyle \mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}} $\mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}$ is Π 2 {\displaystyle \Pi _{2}} $\Pi _{2}$ -complete.
C o n = { e : φ e is total and constant } {\displaystyle \mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ is total and constant}}\}} $\mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ is total and constant}}\}$ is Π 2 {\displaystyle \Pi _{2}} $\Pi _{2}$ -complete.
C o f = { e : W e is cofinite } {\displaystyle \mathrm {Cof} =\{e\,:\,W_{e}{\text{ is cofinite}}\}} $\mathrm {Cof} =\{e\,:\,W_{e}{\text{ is cofinite}}\}$ is Σ 3 {\displaystyle \Sigma _{3}} $\Sigma _{3}$ -complete.
R e c = { e : W e is computable } {\displaystyle \mathrm {Rec} =\{e\,:\,W_{e}{\text{ is computable}}\}} $\mathrm {Rec} =\{e\,:\,W_{e}{\text{ is computable}}\}$ is Σ 3 {\displaystyle \Sigma _{3}} $\Sigma _{3}$ -complete.
E x t = { e : φ e is extendible to a total computable function } {\displaystyle \mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ is extendible to a total computable function}}\}} $\mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ is extendible to a total computable function}}\}$ is Σ 3 {\displaystyle \Sigma _{3}} $\Sigma _{3}$ -complete.
C p l = { e : W e ≡ T H P } {\displaystyle \mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}} $\mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}$ is Σ 4 {\displaystyle \Sigma _{4}} $\Sigma _{4}$ -complete, where H P {\displaystyle \mathrm {HP} } $\mathrm {HP}$ is the halting problem.

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

^ 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

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.