6.4 튜링 기계의 정지 문제와 불완전성 정리의 환원 관계

1. 두 결과의 본질적 동질성

튜링의 정지 문제 결정 불가능성(1936)과 괴델의 불완전성 정리(1931)는 표면적으로 상이한 영역—계산 이론과 메타수학—에 속하지만, 본질적으로 동일한 현상의 상이한 측면을 포착한다. 두 결과는 자기 참조(Self-Reference)와 대각화(Diagonalization)라는 공통 기법에 기반하며, 상호 환원(Mutual Reduction) 가능하다.

2. 정지 문제에서 불완전성으로의 환원

2.1 환원의 구조

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

정리: PA가 무모순하고 $\Sigma_1$ -건전( $\Sigma_1$ -Sound)하면, PA는 불완전하다.

증명: 귀류법. PA가 완전하다고 가정한다.

튜링 기계 $M$ 과 입력 $w$ 에 대해, “ $M$ 이 $w$ 에서 정지한다“를 PA의 $\Sigma_1$ 문장 $\phi_{M,w}$ 로 인코딩한다:

$\phi_{M,w} \equiv \exists t \, \text{Halts}(\ulcorner M \urcorner, \ulcorner w \urcorner, t)$

여기서 $\text{Halts}(m, w, t)$ 는 “튜링 기계 $m$ 이 입력 $w$ 에서 $t$ 단계 이내에 정지한다“를 표현하는 원시 재귀적 관계이다.

PA가 완전하므로, 모든 문장 $\phi_{M,w}$ 에 대해 PA $\vdash \phi_{M,w}$ 또는 PA $\vdash \neg\phi_{M,w}$ 이다.

PA의 정리를 체계적으로 열거하면서 $\phi_{M,w}$ 또는 $\neg\phi_{M,w}$ 의 출현을 대기하면, PA의 완전성에 의해 유한 시간 내에 반드시 둘 중 하나가 나타난다. PA가 $\Sigma_1$ -건전하므로:

PA $\vdash \phi_{M,w}$ 이면 $M$ 이 실제로 $w$ 에서 정지한다.
PA $\vdash \neg\phi_{M,w}$ 이면 $M$ 이 실제로 $w$ 에서 정지하지 않는다.

이 절차는 정지 문제의 결정 알고리즘을 구성하며, 이는 정지 문제의 결정 불가능성에 모순이다. 따라서 PA는 완전하지 않다. $\blacksquare$

환원의 의의

이 환원은 정지 문제의 결정 불가능성이 불완전성 정리를 함의함을 보여준다. 계산 이론적 한계(결정 불가능성)가 메타수학적 한계(불완전성)를 직접 도출한다.

불완전성에서 결정 불가능성으로의 환원

불완전성으로부터의 도출

PA�� 불완전성으로부터 정지 문제의 결정 불가능성을 직접 도출하는 것은 보다 간접적이다. 핵심 연결 고리:

PA에서 결정 불가능한 문장 $G$ 가 존재한다.
$G$ 는 $\Pi_1^0$ 문장이다(“모든 자연수 $x$ 에 대해 $R(x)$ “형태).
“ $G$ 가 PA에서 증명 가능한가?“라는 물음의 결정 불가능성은 PA의 정리 집합 $\text{Th}_\text{PA}$ 의 결정 불가능성의 특수한 경우이다.
$\text{Th}_\text{PA}$ 의 결정 불가능성은 정지 문제의 결정 불가능성으로 환원 가능하다(PA의 정리 열거가 정지 문제와 동등한 난이도를 가짐).

역환원의 정밀화

보다 정밀하게, 다음의 환원이 성립한다:

정지 문제 $\text{HALT}$ 는 PA의 정리 집합 $\text{Th}_\text{PA}$ 에 다대일 환원(Many-One Reducible) 가능하다:

$\text{HALT} \leq_m \text{Th}_\text{PA}$

이 환원에 의해, $\text{Th}_\text{PA}$ 가 결정 가능하면 $\text{HALT}$ 도 결정 가능하다. 대우에 의해, $\text{HALT}$ 가 결정 불가능하면 $\text{Th}_\text{PA}$ 도 결정 불가능하다.

역으로, $\text{Th}_\text{PA}$ 는 $\text{HALT}$ 에 다대일 환원 가능하다:

$\text{Th}_\text{PA} \leq_m \text{HALT}$

이는 PA의 정리 여부를 증명 탐색(정지 확인)으로 환원하는 것이다. 두 환원을 결합하면 $\text{HALT}$ 와 $\text{Th}_\text{PA}$ 는 동일한 튜링 정도(Turing Degree) $\mathbf{0}'$ 에 속한다.

구조적 동형성의 상세 분석

자기 참조의 구조 비교

괴델의 자기 참조: 괴델 수 부여(산술화)에 의해 형식 체계가 자기 자신의 구문론적 성질에 관한 산술적 문장을 표현한다. 대각화 보조 정리에 의해 자기 참조적 괴델 문장이 구성된다.

튜링의 자기 참조: 튜링 기계의 부호화에 의해 튜링 기계가 다른 튜링 기계(또는 자기 자신)를 데이터로 처리한다. 역전 기계 $D$ 가 자기 자신의 부호화를 입력으로 받아 모순적 동작을 수행한다.

역전 메커니즘의 비교

괴델의 역전: $G \leftrightarrow \neg\text{Prov}(\ulcorner G \urcorner)$ — 괴델 문장이 자기 자신의 증명 가능성을 부정한다.

튜링의 역전: $D(\langle D \rangle)$ 가 $H$ 의 판정을 역전한다 — $H$ 가 “정지“라 판정하면 $D$ 는 비정지, 역도 마찬가지.

두 역전 모두 자기 참조적 구성이 판정 메커니즘의 결론을 부정하도록 설계된 것이다.

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

단일한 한계의 이중 표현

정지 문제와 불완전성 정리의 환원 관계는 인공지능에 대해 단일한 한계의 이중 표현을 제공한다:

계산적 관점(정지 문제): AI는 임의의 프로그램의 동작을 일반적으로 예측할 수 없다.
논리적 관점(불완전성): AI는 자기 자신의 추론 체계의 모든 진리를 포착할 수 없다.

이 두 표현은 동일한 근본적 한계—자기 참조에 의한 한계—의 상이한 측면이다.

실용적 함의

환원 관계에 의해, AI의 한계에 관한 결과가 계산 이론과 메타수학 양쪽에서 도출 가능하다. 이는 AI의 한계를 분석하는 도구가 풍부하며, 상이한 관점에서의 분석이 상호 보완적으로 활용 가능함을 의미한다.

한계의 보편성

환원 관계는 불완전성과 결정 불가능성이 특정 형식 체계나 계산 모델에 한정된 현상이 아니라, 충분히 강력한 모든 형식적/계산적 체계에 보편적으로 적용되는 현상임을 확인한다. 이 보편성이 인공지능의 한계가 특정 구현이나 아키텍처에 의존하지 않는 원리적 한계임을 보장한다.