Classes of partial recursive functions
계산-가능성 이론(computability theory) 에서, 인덱스 집합 (index sets )은 계산-가능한 함수(computable functions) 의 클래스를 설명합니다; 구체적으로 특별히, 그것들은 부분 계산-가능한 함수의 고정된 괴델 번호-매김(Gödel numbering) 에 따라 특정 클래스에서 함수의 모든 인덱스를 제공합니다.
Definition
φ
e
{\displaystyle \varphi _{e}}
W
e
{\displaystyle W_{e}}
계산-가능하게 열거-가능 집합(c.e. sets) 의 계산-가능한 열거라고 놓습니다.
A
{\displaystyle {\mathcal {A}}}
A
=
{
x
:
φ
x
∈
A
}
{\displaystyle A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}}
A
{\displaystyle A}
A
{\displaystyle {\mathcal {A}}}
인덱스 집합 (index set )입니다. 일반적으로,
A
{\displaystyle A}
φ
x
≃
φ
y
{\displaystyle \varphi _{x}\simeq \varphi _{y}}
x
,
y
∈
N
{\displaystyle x,y\in \mathbb {N} }
x
∈
A
↔
y
∈
A
{\displaystyle x\in A\leftrightarrow y\in A}
Index sets and Rice's theorem 두 가지 자명한 예외를 제외하고, 대부분의 인덱스 집합은 비-계산가능입니다. 이것은 라이스의 정리(Rice's theorem) 에서 다음과 같이 명시되어 있습니다:
C
{\displaystyle {\mathcal {C}}}
C
{\displaystyle C}
C
{\displaystyle C}
C
{\displaystyle C}
C
{\displaystyle C}
N
{\displaystyle \mathbb {N} }
라이스의 정리는 "부분 계산-가능 함수의 임의의 비-자명한 속성은 비-결정가능이다"라고 말합니다.[1]
Completeness in the arithmetical hierarchy 인덱스 집합은 산술적 계층 구조(arithmetical hierarchy) 의 일부 수준에서 완비인 집합의 많은 예제를 제공합니다. 여기서, 우리는
Σ
n
{\displaystyle \Sigma _{n}}
A
{\displaystyle A}
Σ
n
{\displaystyle \Sigma _{n}}
B
{\displaystyle B}
B
{\displaystyle B}
A
{\displaystyle A}
m-감소(m-reduction) 가 있으면
Σ
n
{\displaystyle \Sigma _{n}}
완비 (complete )라고 말합니다.
Π
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 .경험적으로, 만약 집합
A
{\displaystyle A}
Σ
n
{\displaystyle \Sigma _{n}}
Π
n
{\displaystyle \Pi _{n}}
A
{\displaystyle A}
Σ
n
{\displaystyle \Sigma _{n}}
Π
n
{\displaystyle \Pi _{n}}
Notes
^ 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
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
