5.20 불완전성 정리와 정지 문제의 논리적 등가 관계

1. 두 결과의 개관

괴델의 불완전성 정리(1931)와 튜링의 정지 문제 결정 불가능성(1936)은 각각 형식 체계의 한계와 기계적 계산의 한계를 확정하는 결과이다. 표면적으로 상이한 이 두 결과는 깊은 논리적 연관성을 가지며, 본질적으로 동일한 현상—자기 참조에 의한 한계—의 상이한 측면을 드러낸다.

2. 불완전성 정리에서 정지 문제로

2.1 불완전성에서 결정 불가능성의 도출

불완전성 정리로부터 정지 문제의 결정 불가능성을 도출할 수 있다.

PA에서 결정 불가능한 문장 $G$ 가 존재한다. “ $G$ 가 PA에서 증명 가능한가?“를 판정하는 것이 결정 불가능하다면, 일반적인 증명 가능성 판정도 결정 불가능하다.

보다 직접적으로, PA의 정리들의 집합 $\text{Th}_\text{PA} = \{\ulcorner \phi \urcorner \mid \text{PA} \vdash \phi\}$ 가 결정 불가능(Decidable)하지 않음을 보인다. $\text{Th}_\text{PA}$ 가 결정 가능하면, 임의의 문장 $\phi$ 에 대해 $\phi \in \text{Th}_\text{PA}$ 인지를 판정할 수 있고, PA가 완전하다면 모든 참인 문장이 결정 가능하게 된다. 불완전성 정리에 의해 PA는 불완전하므로, $\text{Th}_\text{PA}$ 는 결정 불가능하다.

이 결정 불가능성은 정지 문제의 결정 불가능성으로 환원된다. 임의의 튜링 기계 $M$ 과 입력 $w$ 에 대해, “ $M$ 이 $w$ 에서 정지한다“를 PA의 문장 $\phi_{M,w}$ 로 인코딩할 수 있으며, 이 인코딩에 의해 정지 문제가 PA의 정리 판정 문제로 환원된다.

3. 정지 문제에서 불완전성으로

3.1 결정 불가능성에서 불완전성의 도출

정지 문제의 결정 불가능성으로부터 불완전성을 도출할 수 있다.

PA가 완전하고 무모순하다고 가정한다. 임의의 문장 $\phi$ 에 대해 PA $\vdash \phi$ 또는 PA $\vdash \neg\phi$ 이다. PA의 정리는 효과적으로 열거 가능하므로(증명을 체계적으로 생성할 수 있으므로), PA의 모든 정리를 열거하면서 $\phi$ 또는 $\neg\phi$ 가 나타나는지를 기다리면, 유한 시간 내에 반드시 둘 중 하나가 나타난다(PA가 완전하므로).

이 절차를 정지 문제에 적용한다. 튜링 기계 $M$ 이 입력 $w$ 에서 정지하는지를 PA의 문장 $\phi_{M,w}$ 로 표현한다. PA가 완전하면, $\phi_{M,w}$ 또는 $\neg\phi_{M,w}$ 의 증명이 유한 시간 내에 발견되므로, 정지 문제가 결정 가능해진다. 이는 정지 문제의 결정 불가능성에 모순이다.

따라서 PA는 완전하지 않다(불완전하다).

4. 자기 참조 구조의 동형성

4.1 괴델의 대각선 논법

괴델 문장 $G$ 의 구성: $G \leftrightarrow \neg\text{Prov}(\ulcorner G \urcorner)$

$G$ 는 자기 자신의 증명 불가능성을 주장한다. 자기 참조는 괴델 수 부여에 의한 대각화(Diagonalization)로 실현된다.

4.2 튜링의 대각선 논법

정지 문제 증명의 역전 기계 $D$ : $D$ 가 자기 자신의 부호화를 입력으로 받을 때 모순적 동작을 수행한다.

$H(\langle D \rangle, \langle D \rangle) = \text{accept}$ 이면 $D$ 는 무한 루프.
$H(\langle D \rangle, \langle D \rangle) = \text{reject}$ 이면 $D$ 는 정지.

$D$ 는 자기 자신의 정지/비정지에 관한 판정을 역전시킨다.

4.3 구조적 동형성

측면	괴델의 불완전성	튜링의 정지 문제
자기 참조 대상	증명 가능성	정지 여부
자기 참조 기제	괴델 수 + 대각화 보조 정리	튜링 기계 부호화 + 자기 입력
역전 메커니즘	$G \leftrightarrow \neg\text{Prov}(\ulcorner G \urcorner)$	$D$ 가 $H$ 의 판정을 역전
모순의 도출	무모순성 가정과의 충돌	정지/비정지의 논리적 모순
결론	결정 불가능 문장의 존재	결정 불가능 문제의 존재
원천 기법	칸토어의 대각선 논법	칸토어의 대각선 논법

두 결과 모두 칸토어의 대각선 논법(1891)의 적용이다. 칸토어가 실수의 비가산성을 증명하기 위해 사용한 “자기 참조에 의한 모순 도출” 기법이 괴델에 의해 형식 체계에, 튜링에 의해 계산 모델에 적용된 것이다.

5. 형식적 등가성

5.1 환원 관계

불완전성 정리와 정지 문제 결정 불가능성은 상호 환원(Mutual Reduction) 가능하다:

정지 문제 → 불완전성: PA에서의 정리 판정 문제가 결정 가능하면 정지 문제도 결정 가능하다. 정지 문제가 결정 불가능하므로, PA의 정리 판정 문제도 결정 불가능하다. PA의 정리 판정이 결정 불가능하면 PA는 불완전하다(완전하면 결정 가능할 것이므로).

불완전성 → 정지 문제: 불완전한 문장의 존재로부터 직접적으로 정지 문제의 결정 불가능성이 도출되지는 않으나, 불완전성의 구성 기법(대각화)이 정지 문제의 결정 불가능성 증명에 핵심적으로 사용된다.

5.2 정밀한 관계

두 결과의 관계를 더 정밀하게 기술하면:

정지 문제의 결정 불가능성은 불완전성 정리를 함의한다(위에서 보인 바와 같이).
불완전성 정리 자체는 정지 문제의 결정 불가능성을 직접 함의하지 않으나, 불완전성 정리의 증명 기법(산술화, 대각화)은 정지 문제의 증명 기법과 본질적으로 동일하다.

6. 통합적 관점: 계산의 근본적 한계

불완전성 정리와 정지 문제는 동일한 근본적 한계의 두 측면이다:

불완전성: 형식 체계는 자기 자신에 관한 모든 진리를 포착할 수 없다.
결정 불가능성: 기계적 절차는 자기 자신에 관한 모든 물음에 답할 수 없다.

두 한계의 공통 원천은 자기 참조(Self-Reference)이다. 충분히 강력한 체계가 자기 자신에 관해 “말할” 수 있을 때, 대각선 논법에 의해 체계가 자기 자신에 관해 올바르게 답할 수 없는 물음이 구성된다. 이 자기 참조적 한계는 형식 체계, 튜링 기계, 람다 대수, 재귀 함수 등 모든 계산 모델에 공통적으로 적용되며, 계산이라는 개념의 본질적 경계를 형성한다.

7. 인공지능에 대한 통합적 함의

불완전성 정리와 정지 문제의 등가 관계는 인공지능에 대해 통합된 한계를 부과한다. 인공지능 체계가 형식 체계로 모델링되든 튜링 기계로 모델링되든, 자기 참조에 의한 한계로부터 자유로울 수 없다. 이는 “자기 자신의 정확성을 완전히 검증하는 AI”, “모든 수학적 진리를 발견하는 AI”, “모든 프로그램의 종료 여부를 판별하는 AI“가 원리적으로 불가능함을 의미한다.