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}}
W
e
{\displaystyle W_{e}}
c.e. sets .
Let
A
{\displaystyle {\mathcal {A}}}
A
=
{
x
:
φ
x
∈
A
}
{\displaystyle A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}}
A
{\displaystyle A}
index set of
A
{\displaystyle {\mathcal {A}}}
A
{\displaystyle A}
x
,
y
∈
N
{\displaystyle x,y\in \mathbb {N} }
φ
x
≃
φ
y
{\displaystyle \varphi _{x}\simeq \varphi _{y}}
x
∈
A
↔
y
∈
A
{\displaystyle x\in A\leftrightarrow y\in A}
[ edit ] Most index sets are non-computable, aside from two trivial exceptions. This is stated in Rice's theorem :
Let
C
{\displaystyle {\mathcal {C}}}
C
{\displaystyle C}
C
{\displaystyle C}
C
{\displaystyle C}
C
{\displaystyle C}
N
{\displaystyle \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}}
A
{\displaystyle A}
Σ
n
{\displaystyle \Sigma _{n}}
Σ
n
{\displaystyle \Sigma _{n}}
B
{\displaystyle B}
m-reduction from
B
{\displaystyle B}
A
{\displaystyle A}
Π
n
{\displaystyle \Pi _{n}}
[ 2]
E
m
p
=
{
e
:
W
e
=
∅
}
{\displaystyle \mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}}
Π
1
{\displaystyle \Pi _{1}}
F
i
n
=
{
e
:
W
e
is finite
}
{\displaystyle \mathrm {Fin} =\{e\,:\,W_{e}{\text{ is finite}}\}}
Σ
2
{\displaystyle \Sigma _{2}}
I
n
f
=
{
e
:
W
e
is infinite
}
{\displaystyle \mathrm {Inf} =\{e\,:\,W_{e}{\text{ is infinite}}\}}
Π
2
{\displaystyle \Pi _{2}}
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} \}}
Π
2
{\displaystyle \Pi _{2}}
C
o
n
=
{
e
:
φ
e
is total and constant
}
{\displaystyle \mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ is total and constant}}\}}
Π
2
{\displaystyle \Pi _{2}}
C
o
f
=
{
e
:
W
e
is cofinite
}
{\displaystyle \mathrm {Cof} =\{e\,:\,W_{e}{\text{ is cofinite}}\}}
Σ
3
{\displaystyle \Sigma _{3}}
R
e
c
=
{
e
:
W
e
is computable
}
{\displaystyle \mathrm {Rec} =\{e\,:\,W_{e}{\text{ is computable}}\}}
Σ
3
{\displaystyle \Sigma _{3}}
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}}\}}
Σ
3
{\displaystyle \Sigma _{3}}
C
p
l
=
{
e
:
W
e
≡
T
H
P
}
{\displaystyle \mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}}
Σ
4
{\displaystyle \Sigma _{4}}
H
P
{\displaystyle \mathrm {HP} }
halting problem .Empirically, if the "most obvious" definition of a set
A
{\displaystyle A}
Σ
n
{\displaystyle \Sigma _{n}}
Π
n
{\displaystyle \Pi _{n}}
A
{\displaystyle A}
Σ
n
{\displaystyle \Sigma _{n}}
Π
n
{\displaystyle \Pi _{n}}
^ Odifreddi, P. G. Classical Recursion Theory, Volume 1 . ^ 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 
