계산-가능성 이론(computability theory)에서, 인덱스 집합(index sets)은 계산-가능한 함수(computable functions)의 클래스를 설명합니다; 구체적으로 특별히, 그것들은 부분 계산-가능한 함수의 고정된 괴델 번호-매김(Gödel numbering)에 따라 특정 클래스에서 함수의 모든 인덱스를 제공합니다.
Definition
\(\varphi_e\)를 모든 부분 계산-가능한 함수의 계산-가능한 열거라고 놓고, \(W_{e}\)를 모든 계산-가능하게 열거-가능 집합(c.e. sets)의 계산-가능한 열거라고 놓습니다.
\(\mathcal{A}\)를 부분 계산-가능한 함수의 클래스라고 놓습니다. 만약 \(A = \{x \,:\, \varphi_{x} \in \mathcal{A} \}\)이면, \(A\)는 \(\mathcal{A}\)의 인덱스 집합(index set)입니다. 일반적으로, \(A\)는 만약 \(\varphi_x \simeq \varphi_y\)를 갖는 모든 각 \(x,y \in \mathbb{N}\)에 대해 (즉, 그것들이 같은 함수를 인덱스하면), \(x \in A \leftrightarrow y \in A\)를 가지는 인덱스 집합입니다. 직관적으로, 이것들은 그것들이 인덱스하는 함수에 대한 참조로만 설명하는 자연수의 집합입니다.
Index sets and Rice's theorem
두 가지 자명한 예외를 제외하고, 대부분의 인덱스 집합은 비-계산가능입니다. 이것은 라이스의 정리(Rice's theorem)에서 다음과 같이 명시되어 있습니다:
\(\mathcal{C}\)를 인덱스 집합 \(C\)를 갖는 부분 계산-가능 함수의 클래스라고 놓습니다. 그런-다음 \(C\)는 계산-가능인 것과 \(C\)가 빈 것, 또는 \(C\)가 모두 \(\mathbb{N}\)인 것은 필요충분 조건입니다.
라이스의 정리는 "부분 계산-가능 함수의 임의의 비-자명한 속성은 비-결정가능이다"라고 말합니다.
Completeness in the arithmetical hierarchy
인덱스 집합은 산술적 계층 구조(arithmetical hierarchy)의 일부 수준에서 완비인 집합의 많은 예제를 제공합니다. 여기서, 우리는 \(\Sigma_n\) 집합 \(A\)는 만약, 모든 각 \(\Sigma_n\) 집합 \(B\)에 대해, \(B\)에서 \(A\)로의 m-감소(m-reduction)가 있으면 \(\Sigma_n\)-완비(complete)라고 말합니다. \(\Pi_n\)-완비성도 유사하게 정의됩니다. 여기 몇 가지 예제가 있습니다:
- \(\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.
경험적으로, 만약 집합 \(A\)의 "가장 명백한" 정의가 \(\Sigma_n\) [각각, \(\Pi_n\)]이면, 우리는 보통 \(A\)가 \(\Sigma_n\)-완비 [각각, \(\Pi_n\)-완비]임을 보여줄 수 있습니다.
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.