3.18 정지 문제의 결정 불가능성 대각선 논법 증명

1. 대각선 논법의 기원

대각선 논법(Diagonalization Argument)은 칸토어(Georg Cantor)가 1891년 실수의 비가산성(Uncountability of Real Numbers)을 증명하기 위해 사용한 증명 기법이다. 칸토어는 자연수에서 실수로의 전사 함수(Surjection)가 존재한다고 가정하고, 대각선 원소를 변형하여 이 함수의 치역에 포함되지 않는 실수를 구성함으로써 모순을 도출하였다.

튜링은 칸토어의 대각선 논법을 계산 이론에 적용하여, 정지 문제(Halting Problem)의 결정 불가능성(Undecidability)을 증명하였다.

2. 정리의 진술

정리: 정지 문제의 언어 $\text{HALT} = \{\langle M, w \rangle \mid M \text{이 } w \text{에 대해 정지한다}\}$ 는 결정 불가능(Undecidable)하다. 즉, 모든 입력 $\langle M, w \rangle$ 에 대해 $\langle M, w \rangle \in \text{HALT}$ 인지 아닌지를 올바르게 판정하고 정지하는 튜링 기계(결정기)는 존재하지 않는다.

3. 증명

증명은 귀류법(Proof by Contradiction)으로 진행한다.

3.1 단계 1: 결정기의 가정

정지 문제를 결정하는 튜링 기계 $H$ 가 존재한다고 가정한다. $H$ 는 다음과 같이 동작한다:

$H(\langle M, w \rangle) = \begin{cases} \text{accept} & \text{if } M \text{ halts on } w \\ \text{reject} & \text{if } M \text{ does not halt on } w \end{cases}$

$H$ 는 모든 입력에 대해 반드시 정지하며, 올바른 판정을 내린다.

단계 2: 역전 기계 $D$ 의 구성

$H$ 를 이용하여 새로운 튜링 기계 $D$ 를 구성한다. $D$ 는 튜링 기계의 부호화 $\langle M \rangle$ 을 입력으로 받아 다음과 같이 동작한다:

$H(\langle M, \langle M \rangle \rangle)$ 를 실행한다. 즉, $H$ 에게 “기계 $M$ 이 자기 자신의 부호화 $\langle M \rangle$ 을 입력으로 받을 때 정지하는가?“를 묻는다.
$H$ 가 “수락(정지함)“을 출력하면, $D$ 는 무한 루프(Infinite Loop)에 진입한다.
$H$ 가 “거부(정지하지 않음)“를 출력하면, $D$ 는 정지(수락)한다.

형식적으로:

$D(\langle M \rangle) = \begin{cases} \text{loop forever} & \text{if } H(\langle M, \langle M \rangle \rangle) = \text{accept} \\ \text{halt (accept)} & \text{if } H(\langle M, \langle M \rangle \rangle) = \text{reject} \end{cases}$

$D$ 의 핵심적 특성은 $H$ 의 판정 결과를 역전(Invert)한다는 것이다. $H$ 가 “정지함“이라고 판정하면 $D$ 는 정지하지 않고, “정지하지 않음“이라고 판정하면 $D$ 는 정지한다.

3.2 단계 3: 자기 참조에 의한 모순

$D$ 에 자기 자신의 부호화 $\langle D \rangle$ 를 입력으로 제공한다. $D(\langle D \rangle)$ 의 동작을 분석한다.

경우 1: $D(\langle D \rangle)$ 가 정지한다고 가정한다.

$D$ 의 정의에 의해, $D$ 가 $\langle D \rangle$ 에 대해 정지한 것은 $H(\langle D, \langle D \rangle \rangle)$ 가 “거부“를 출력한 경우이다.
$H$ 의 정의에 의해, $H$ 가 “거부“를 출력한 것은 $D$ 가 $\langle D \rangle$ 에 대해 정지하지 않는 경우이다.
따라서 $D$ 가 $\langle D \rangle$ 에 대해 정지한다 → $D$ 가 $\langle D \rangle$ 에 대해 정지하지 않는다. 모순.

경우 2: $D(\langle D \rangle)$ 가 정지하지 않는다고 가정한다.

$D$ 의 정의에 의해, $D$ 가 $\langle D \rangle$ 에 대해 정지하지 않은 것은 $H(\langle D, \langle D \rangle \rangle)$ 가 “수락“을 출력한 경우이다.
$H$ 의 정의에 의해, $H$ 가 “수락“을 출력한 것은 $D$ 가 $\langle D \rangle$ 에 대해 정지하는 경우이다.
따라서 $D$ 가 $\langle D \rangle$ 에 대해 정지하지 않는다 → $D$ 가 $\langle D \rangle$ 에 대해 정지한다. 모순.

3.3 단계 4: 결론

두 경우 모두 모순이 발생한다. 따라서 처음의 가정—정지 문제를 결정하는 튜링 기계 $H$ 가 존재한다—이 거짓이다.

$\therefore \text{HALT는 결정 불가능하다.} \quad \blacksquare$

대각선 논법의 구조 분석

이 증명이 “대각선” 논법으로 불리는 이유를 설명한다. 모든 튜링 기계를 $M_1, M_2, M_3, \ldots$ 로 열거하고, 정지 여부를 다음의 무한 행렬로 표현한다:

	$\langle M_1 \rangle$	$\langle M_2 \rangle$	$\langle M_3 \rangle$	$\cdots$
$M_1$	$h_{11}$	$h_{12}$	$h_{13}$	$\cdots$
$M_2$	$h_{21}$	$h_{22}$	$h_{23}$	$\cdots$
$M_3$	$h_{31}$	$h_{32}$	$h_{33}$	$\cdots$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$

여기서 $h_{ij} = 1$ 이면 $M_i$ 가 $\langle M_j \rangle$ 에 대해 정지하고, $h_{ij} = 0$ 이면 정지하지 않는다.

기계 $D$ 는 대각선 원소 $h_{ii}$ 를 역전하여 구성된다:

$D$ 가 $\langle M_i \rangle$ 에 대해 정지하는 것은 $h_{ii} = 0$ 인 것과 동치

$D$ 자체도 어떤 $M_k$ 이므로, $D$ 의 대각선 원소 $h_{kk}$ 에 대해:

$h_{kk} = 1$ 이면 $D$ 는 $\langle M_k \rangle = \langle D \rangle$ 에 대해 정지하지 않으므로 $h_{kk} = 0$ . 모순.
$h_{kk} = 0$ 이면 $D$ 는 $\langle D \rangle$ 에 대해 정지하므로 $h_{kk} = 1$ . 모순.

이 구조가 칸토어의 대각선 논법과 동일하다.

증명의 핵심 요소

자기 참조(Self-Reference)

$D$ 가 자기 자신의 부호화 $\langle D \rangle$ 를 입력으로 받는 것이 모순의 근원이다. 이 자기 참조는 “이 문장은 거짓이다“라는 거짓말쟁이 역리(Liar’s Paradox)와 구조적으로 유사하며, 괴델의 불완전성 정리에서 자기 참조적 명제의 구성과도 동형이다.

역전(Inversion)

$D$ 가 $H$ 의 판정 결과를 역전시키는 것이 모순을 생성하는 메커니즘이다. $H$ 가 “정지함“을 판정하면 $D$ 는 정지하지 않고, 역도 마찬가지이므로, $D$ 의 자기 참조적 동작이 $H$ 의 판정을 무효화한다.

보편성(Universality)

보편 튜링 기계의 존재에 의해 $D$ 의 구성이 가능하다. $D$ 내부에서 $H$ 를 서브루틴으로 호출하고, $M$ 을 시뮬레이션하는 것이 모두 가능해야 한다.

정지 문제 결정 불가능성의 파급 효과

정지 문제의 결정 불가능성으로부터 다수의 다른 결정 불가능성 결과가 환원(Reduction)에 의해 도출된다:

라이스의 정리(Rice’s Theorem): 튜링 기계가 계산하는 함수의 모든 비자명(Nontrivial) 성질은 결정 불가능하다.
힐베르트의 10번째 문제: 디오판토스 방정식의 정수 해 존재를 판정하는 일반적 알고리즘이 존재하지 않는다(마티야세비치, 1970).
동치 문제(Equivalence Problem): 두 튜링 기계가 동일한 언어를 인식하는지를 판정하는 것은 결정 불가능하다.

정지 문제의 결정 불가능성은 기계적 계산의 근본적 한계를 확정하는 결과이며, 인공지능을 포함한 모든 알고리즘 기반 체계의 원리적 능력 범위를 규정한다.