4.17 클레이니의 재귀 정리(Recursion Theorem)와 자기 참조

1. 재귀 정리의 배경

클레이니의 재귀 정리(Kleene’s Recursion Theorem, 또는 고정점 정리, Fixed-Point Theorem)는 스티븐 클레이니(Stephen Kleene)가 1938년에 증명한 재귀 함수 이론의 핵심 결과이다. 이 정리는 튜링 기계(또는 재귀 함수)가 자기 자신의 부호화(Description)에 접근할 수 있음을 보장하는 형식적 결과이며, 자기 참조(Self-Reference)의 수학적 기반을 제공한다.

2. 정리의 진술

2.1 제1형태 (고정점 정리)

모든 전재귀 함수(Total Recursive Function) $t: \mathbb{N} \rightarrow \mathbb{N}$ 에 대해, 다음을 만족하는 자연수 $n$ 이 존재한다:

$\varphi_n = \varphi_{t(n)}$

여기서 $\varphi_e$ 는 인덱스(Gödel Number) $e$ 를 가진 부분 재귀 함수이다. 즉, 프로그램 $n$ 과 프로그램 $t(n)$ 은 동일한 함수를 계산한다.

이 형태는 임의의 “프로그램 변환” $t$ 에 대해, $t$ 에 의해 변환되어도 동작이 변하지 않는 프로그램(고정점)이 존재함을 보장한다.

제2형태 (자기 참조 정리)

모든 부분 재귀 함수 $f(x, y)$ 에 대해, 다음을 만족하는 인덱스 $e$ 가 존재한다:

$\varphi_e(y) = f(e, y) \quad \text{(모든 } y \text{에 대해)}$

즉, 프로그램 $e$ 는 자기 자신의 인덱스 $e$ 를 “알고 있으며”, 이를 입력으로 사용하여 함수 $f$ 를 계산한다.

3. 증명의 핵심 아이디어

3.1 s-m-n 정리의 활용

증명은 클레이니의 s-m-n 정리(s-m-n Theorem, 또는 매개변수 정리, Parametrization Theorem)를 핵심적으로 활용한다.

s-m-n 정리: 전재귀 함수 $s: \mathbb{N}^2 \rightarrow \mathbb{N}$ 가 존재하여, 모든 $e, x, y$ 에 대해:

$\varphi_{s(e, x)}(y) = \varphi_e(x, y)$

이 정리는 2-항 함수 $\varphi_e(x, y)$ 에서 첫 번째 인자 $x$ 를 “고정“하여 1-항 함수 $\varphi_{s(e,x)}(y)$ 를 생성하는 효과적 절차가 존재함을 보장한다. 이는 부분 적용(Partial Application) 또는 커링(Currying)의 재귀 함수 이론적 형식화이다.

제2형태의 증명 개요

$f(x, y)$ 가 주어졌을 때:

보조 함수 $d(x, y) = f(s(x, x), y)$ 를 정의한다. $d$ 는 $f$ 와 $s$ 로부터 합성에 의해 구성되므로 부분 재귀적이다.
$d$ 의 인덱스를 $e_0$ 라 하자: $\varphi_{e_0}(x, y) = d(x, y) = f(s(x, x), y)$ .
$e = s(e_0, e_0)$ 로 정의한다.
그러면:

$\varphi_e(y) = \varphi_{s(e_0, e_0)}(y) = \varphi_{e_0}(e_0, y) = d(e_0, y) = f(s(e_0, e_0), y) = f(e, y)$

따라서 $\varphi_e(y) = f(e, y)$ 이며, $e$ 가 원하는 고정점이다. $\blacksquare$

4. 재귀 정리의 응용

4.1 자기 복제 프로그램(Quine)

재귀 정리는 자기 자신의 소스 코드를 출력하는 프로그램(Quine)의 존재를 보장한다.

$f(e, y) = e$ (입력 $y$ 에 무관하게 자기 자신의 인덱스 $e$ 를 출력)로 설정하면, 재귀 정리에 의해 $\varphi_e(y) = e$ 인 인덱스 $e$ 가 존재한다. 이 프로그램은 자기 자신의 부호화를 출력한다.

4.2 컴퓨터 바이러스의 존재 가능성

재귀 정리는 자기 자신을 복제하는 프로그램(자기 복제 프로그램)의 존재를 이론적으로 보장한다. 프로그램이 자기 자신의 코드에 접근하여 이를 다른 프로그램에 삽입할 수 있으므로, 컴퓨터 바이러스의 존재는 수학적으로 불가피하다.

4.3 괴델 문장의 구성

괴델의 불완전성 정리에서 자기 참조적 문장 “ $G$ : 이 문장은 증명 불가능하다“의 구성은 재귀 정리(또는 그 선행 형태인 대각선 보조정리)에 기반한다. 형식 체계 내에서 문장이 자기 자신의 증명 불가능성을 주장하는 것이 가능한 것은 자기 참조의 형식적 구현 가능성 때문이다.

4.4 결정 불가능성 증명

정지 문제의 결정 불가능성 증명에서 기계 $D$ 가 자기 자신의 부호화 $\langle D \rangle$ 를 입력으로 받아 모순적 동작을 수행하는 구성은 재귀 정리의 응용이다.

4.5 라이스의 정리(Rice’s Theorem)

정리: 부분 재귀 함수의 모든 비자명(Nontrivial) 성질은 결정 불가능하다.

형식적으로: $\mathcal{C}$ 가 부분 재귀 함수의 집합으로서 $\emptyset \neq \mathcal{C} \neq \text{(모든 부분 재귀 함수)}$ 이면, $\{e \mid \varphi_e \in \mathcal{C}\}$ 는 재귀적이지 않다(결정 불가능).

라이스의 정리의 증명에서 재귀 정리가 핵심적으로 사용된다.

5. 재귀 정리와 대각선 논법의 관계

재귀 정리는 칸토어의 대각선 논법(Diagonalization)과 깊이 연관된다. 대각선 논법이 “자기 자신에 적용된 함수“의 구성에 의해 모순을 도출하는 부정적 결과(존재 불가능성 증명)에 사용되는 반면, 재귀 정리는 “자기 자신에 접근하는 프로그램“의 존재를 보장하는 긍정적 결과이다.

대각선 논법: 자기 참조에 의해 모순이 발생 → 가정의 부정 (부정적)
재귀 정리: 자기 참조가 일관되게 가능 → 고정점의 존재 (긍정적)

두 결과는 자기 참조라는 동일한 현상의 상보적 측면을 포착한다.

6. 재귀 정리의 이론적 의의

클레이니의 재귀 정리는 계산 이론에서 자기 참조(Self-Reference)의 형식적 가능성을 확립한 근본 정리이다. 이 정리는 프로그램이 자기 자신의 코드에 접근하고, 자기 자신을 데이터로 처리할 수 있음을 수학적으로 보장하며, 이 가능성이 괴델의 불완전성 정리, 정지 문제의 결정 불가능성, 라이스의 정리, 폰 노이만의 자기 복제 이론, 그리고 현대 컴퓨터 바이러스의 이론적 기반을 구성한다.