4.21 열거 가능성(Enumerability)과 결정 가능성(Decidability)의 구분

1. 두 개념의 정의

열거 가능성(Enumerability)과 결정 가능성(Decidability)은 계산 이론에서 집합의 알고리즘적 성질을 기술하는 두 핵심 개념이며, 이 둘의 구분은 계산 가능성 이론의 근본적 구조를 형성한다.

1.1 결정 가능성(Decidability)

집합 $A \subseteq \mathbb{N}$ 이 결정 가능(Decidable)하다 함은, 임의의 $x \in \mathbb{N}$ 에 대해 $x \in A$ 인지 $x \notin A$ 인지를 항상 올바르게 판정하고 정지하는 알고리즘(결정기, Decider)이 존재함을 의미한다.

형식적으로, $A$ 가 결정 가능인 것은 $A$ 의 특성 함수 $\chi_A$ 가 전계산 가능(Total Computable)인 것과 동치이다:

$\chi_A(x) = \begin{cases} 1 & \text{if } x \in A \\ 0 & \text{if } x \notin A \end{cases}$

열거 가능성(Enumerability, RE)

집합 $A \subseteq \mathbb{N}$ 이 재귀적으로 열거 가능(Recursively Enumerable, RE)하다 함은, $A$ 의 원소를 하나씩 나열하는 알고리즘(열거기, Enumerator)이 존재함을 의미한다. 동등하게, $A$ 를 인식하는 튜링 기계가 존재함을 의미한다.

$A$ 가 RE인 것의 동등한 특성화:

$A$ 를 인식하는 튜링 기계 $M$ 이 존재한다: $x \in A$ 이면 $M$ 이 $x$ 를 수락하고, $x \notin A$ 이면 $M$ 이 $x$ 를 거부하거나 정지하지 않는다.
부분 계산 가능 함수 $f$ 가 존재하여 $A = \text{dom}(f) = \{x \mid f(x) \text{ is defined}\}$ .
$A = \emptyset$ 이거나, 전계산 가능 함수 $g$ 가 존재하여 $A = \text{range}(g) = \{g(0), g(1), g(2), \ldots\}$ .

결정 가능과 RE의 관계

포함 관계

$\text{결정 가능 집합} \subsetneq \text{RE 집합} \subsetneq \mathcal{P}(\mathbb{N})$

모든 결정 가능 집합은 RE이다. 결정기가 존재하면 이를 인식기로 사용할 수 있기 때문이다. 그러나 역은 성립하지 않는다.

1.2 분리 예시

RE이지만 결정 불가능: $K = \{e \mid \varphi_e(e) \text{ is defined}\}$ (대각 정지 집합). $K$ 는 RE이다(보편 튜링 기계로 시뮬레이션하여 정지 여부를 확인 가능). 그러나 $K$ 는 결정 불가능하다(정지 문제의 특수한 경우).

RE가 아닌 집합: $\overline{K} = \{e \mid \varphi_e(e) \text{ is undefined}\}$ . $K$ 가 RE이고 $\overline{K}$ 가 RE가 아니므로(만약 $\overline{K}$ 가 RE이면 $K$ 가 결정 가능하게 되어 모순), $\overline{K}$ 는 RE가 아니다.

2. 보집합 정리(Complement Theorem)

정리: 집합 $A$ 가 결정 가능인 것은 $A$ 와 $\overline{A}$ 가 모두 RE인 것과 동치이다.

$A \text{ decidable} \iff A \in \text{RE} \wedge \overline{A} \in \text{RE}$

증명

( $\Rightarrow$ ): $A$ 가 결정 가능하면 $\chi_A$ 가 전계산 가능이다. $A$ 를 인식하는 기계: $\chi_A(x) = 1$ 이면 수락, $= 0$ 이면 거부. $\overline{A}$ 를 인식하는 기계: $\chi_A(x) = 0$ 이면 수락, $= 1$ 이면 거부. 따라서 $A$ 와 $\overline{A}$ 모두 RE.

( $\Leftarrow$ ): $A$ 를 인식하는 기계 $M_1$ 과 $\overline{A}$ 를 인식하는 기계 $M_2$ 가 존재한다. 입력 $x$ 에 대해 $M_1$ 과 $M_2$ 를 교대로 한 단계씩 시뮬레이션한다. $x \in A$ 이면 $M_1$ 이 유한 단계 후 수락하고, $x \notin A$ 이면 $M_2$ 가 유한 단계 후 수락한다. 두 경우 모두 유한 시간 내에 판정이 완료되므로, $A$ 는 결정 가능하다.

산술 계층(Arithmetical Hierarchy)

RE 집합과 결정 가능 집합의 관계는 산술 계층(Arithmetical Hierarchy)으로 일반화된다.

$\Sigma_0^0 = \Pi_0^0 = \Delta_0^0$ : 결정 가능 집합
$\Sigma_1^0$ : RE 집합 ( $\exists y \, R(x, y)$ 형태, $R$ 결정 가능)
$\Pi_1^0$ : co-RE 집합 ( $\forall y \, R(x, y)$ 형태, $R$ 결정 가능)
$\Delta_1^0 = \Sigma_1^0 \cap \Pi_1^0$ : 결정 가능 집합 (보집합 정리에 의해)
$\Sigma_n^0$ : $n$ 개의 교대 양화사로 시작하는 ( $\exists \forall \exists \cdots$ ) 산술 관계에 의해 정의되는 집합
$\Pi_n^0$ : $n$ 개의 교대 양화사로 시작하는 ( $\forall \exists \forall \cdots$ ) 산술 관계에 의해 정의되는 집합

계층의 엄격한 분리

$\Sigma_n^0 \subsetneq \Sigma_{n+1}^0, \quad \Pi_n^0 \subsetneq \Pi_{n+1}^0$

각 수준은 이전 수준보다 엄격히 더 큰 집합 클래스를 포함한다. 이 엄격한 분리는 결정 불가능성의 “정도“가 무한히 세분화될 수 있음을 보여준다.

3. 결정 가능성과 열거 가능성의 직관적 비교

측면	결정 가능성	열거 가능성(RE)
물음에 대한 답변	“예” 또는 “아니오” 항상 제공	“예“만 제공 가능, “아니오“는 보장 없음
알고리즘 종료	모든 입력에서 종료	긍정적 입력에서만 종료 보장
프로그래밍 대응	반드시 종료하는 프로그램	종료하지 않을 수 있는 프로그램
보집합에 대한 폐쇄	폐쇄적 ( $A$ 결정 가능이면 $\overline{A}$ 도 결정 가능)	폐쇄적이지 않음
합집합에 대한 폐쇄	폐쇄적	폐쇄적
교집합에 대한 폐쇄	폐쇄적	폐쇄적

4. 인공지능에 대한 함의

열거 가능성과 결정 가능성의 구분은 인공지능의 능력 범위를 정밀하게 규정한다.

검증(Verification) vs 탐색(Search): RE 문제에 대해 인공지능은 해(Solution)가 존재할 때 이를 찾을 수 있으나, 해가 존재하지 않을 때 이를 확인하는 것은 보장되지 않는다. 결정 가능 문제에 대해서는 해의 존재와 부재 모두를 확인할 수 있다.

프로그램 분석의 한계: 프로그램의 동작에 관한 많은 성질이 RE이지만 결정 불가능하다. 예를 들어, “이 프로그램이 정지하는가?“는 RE(정지하면 확인 가능)이지만 결정 불가능(정지하지 않으면 확인 불가)하다.

열거 가능성과 결정 가능성의 구분은 알고리즘적 문제의 난이도를 분류하는 가장 근본적인 틀이며, 이 분류가 인공지능을 포함한 모든 알고리즘 기반 체계의 능력과 한계를 규정한다.