4.14 쿠르트 괴델의 일반 재귀 함수(General Recursive Functions)

1. 괴델의 재귀 함수 연구 배경

쿠르트 괴델(Kurt Gödel, 1906–1978)은 1931년 불완전성 정리의 증명에서 원시 재귀 함수(Primitive Recursive Function)의 개념을 핵심적으로 사용하였다. 괴델 수(Gödel Number)에 의한 형식 체계의 산술화(Arithmetization)는 원시 재귀 함수에 의해 수행되며, 이 과정이 자기 참조적 문장의 구성을 가능하게 하였다.

1934년 프린스턴 대학교에서의 강의에서 괴델은 헤르브란트(Jacques Herbrand)와의 서신(1931)에 기반하여 일반 재귀 함수(General Recursive Function)의 개념을 제시하였다. 이 개념은 원시 재귀 함수를 확장하여 “효과적으로 계산 가능한 함수“의 형식적 포착을 시도한 것이다.

2. 원시 재귀 함수(Primitive Recursive Functions)

2.1 기초 함수(Basic Functions)

원시 재귀 함수의 구성을 위한 세 가지 기초 함수:

영 함수(Zero Function): $Z(x) = 0$ (모든 $x$ 에 대해 0을 반환)
후자 함수(Successor Function): $S(x) = x + 1$
사영 함수(Projection Function): $P_i^n(x_1, \ldots, x_n) = x_i$ ( $n$ 개 인자 중 $i$ 번째를 반환)

2.2 구성 연산(Construction Operations)

기초 함수로부터 새로운 함수를 구성하는 두 가지 연산:

합성(Composition): $g$ 가 $k$ -항 함수이고 $h_1, \ldots, h_k$ 가 $n$ -항 함수이면:

$f(x_1, \ldots, x_n) = g(h_1(x_1, \ldots, x_n), \ldots, h_k(x_1, \ldots, x_n))$

원시 재귀(Primitive Recursion): $g$ 가 $n$ -항 함수이고 $h$ 가 $(n+2)$ -항 함수이면:

$f(x_1, \ldots, x_n, 0) = g(x_1, \ldots, x_n)$
$f(x_1, \ldots, x_n, y+1) = h(x_1, \ldots, x_n, y, f(x_1, \ldots, x_n, y))$

원시 재귀 함수의 예

기초 함수와 합성, 원시 재귀에 의해 구성되는 함수:

덧셈: $\text{add}(x, 0) = x$ , $\text{add}(x, y+1) = S(\text{add}(x, y))$
곱셈: $\text{mult}(x, 0) = 0$ , $\text{mult}(x, y+1) = \text{add}(x, \text{mult}(x, y))$
거듭제곱: $\text{exp}(x, 0) = 1$ , $\text{exp}(x, y+1) = \text{mult}(x, \text{exp}(x, y))$
선행자: $\text{pred}(0) = 0$ , $\text{pred}(y+1) = y$
제한 뺄셈: $\text{monus}(x, 0) = x$ , $\text{monus}(x, y+1) = \text{pred}(\text{monus}(x, y))$

원시 재귀 함수의 한계

원시 재귀 함수는 강력하지만 모든 계산 가능 함수를 포괄하지 못한다. 아커만(Wilhelm Ackermann)이 1928년에 발견한 아커만 함수(Ackermann Function)는 계산 가능하지만 원시 재귀적이지 않다.

아커만 함수의 정의:

$A(0, n) = n + 1$
$A(m+1, 0) = A(m, 1)$
$A(m+1, n+1) = A(m, A(m+1, n))$

아커만 함수는 원시 재귀 함수보다 빠르게 성장하며, 어떤 원시 재귀 함수에 의해서도 상계(Upper Bound)될 수 없다. 이는 원시 재귀 함수의 클래스가 모든 계산 가능 함수를 포괄하기에 불충분함을 보여준다.

3. 일반 재귀 함수(General Recursive Functions)

3.1 무한화 연산자(μ-Operator, Minimization)

원시 재귀 함수의 한계를 극복하기 위해, 무한화 연산자(μ-Operator)가 추가된다.

$g$ 가 $(n+1)$ -항 전재귀 함수이면, 무한화에 의해 정의되는 $n$ -항 함수 $f$ 는:

$f(x_1, \ldots, x_n) = \mu y [g(x_1, \ldots, x_n, y) = 0]$

여기서 $\mu y [P(y)]$ 는 “조건 $P(y)$ 를 만족하는 가장 작은 자연수 $y$ “를 의미한다. 이러한 $y$ 가 존재하지 않으면 $f$ 는 해당 입력에 대해 정의되지 않는다(부분 함수).

형식적 정의

일반 재귀 함수(뮤 재귀 함수, μ-Recursive Function)의 클래스는:

기초 함수(영 함수, 후자 함수, 사영 함수)
합성(Composition)
원시 재귀(Primitive Recursion)
무한화( $\mu$ -Operator)

에 의해 생성되는 부분 함수(Partial Function)의 클래스이다.

전재귀 함수(Total Recursive Function)는 모든 입력에 대해 정의된(즉, 항상 정지하는) 일반 재귀 함수이다.

괴델-헤르브란트의 원래 정의

괴델이 1934년 강의에서 제시한 원래 정의는 무한화 연산자가 아닌 방정식 체계(System of Equations)에 기반한다. 함수 $f$ 는 다음과 같이 정의된다:

기초 함수들과 재귀 방정식의 유한 집합이 주어지고, 이 방정식 체계로부터 등식 추론 규칙(대입, 등식의 추이성 등)에 의해 $f(a_1, \ldots, a_n) = b$ 형태의 등식이 유도 가능하면, $f(a_1, \ldots, a_n)$ 의 값은 $b$ 이다.

클레이니(Stephen Kleene)는 이 방정식 기반 정의가 무한화 연산자를 사용한 정의와 동등함을 증명하였다.

일반 재귀 함수 = 튜링 계산 가능 함수 = 람다 정의 가능 함수

세 가지 독립적 형식화의 동치성:

클레이니(1936): 일반 재귀 함수 = 람다 정의 가능 함수
튜링(1936): 람다 정의 가능 함수 = 튜링 계산 가능 함수
결합: 일반 재귀 함수 = 튜링 계산 가능 함수 = 람다 정의 가능 함수

이 동치성은 세 상이한 형식화가 동일한 함수 클래스를 정의함을 보여주며, 이 클래스가 “효과적으로 계산 가능한 함수“의 올바른 형식적 포착이라는 처치-튜링 명제(Church-Turing Thesis)의 핵심적 근거이다.

재귀 함수 계층

일반 재귀 함수에 의해 다음의 함수 계층이 형성된다:

$\text{기초 함수} \subset \text{원시 재귀 함수} \subset \text{전재귀 함수} \subset \text{부분 재귀 함수}$

각 포함은 엄격하다:

기초 함수 $\subsetneq$ 원시 재귀 함수: 덧셈은 원시 재귀이지만 기초 함수의 단순 합성이 아니다.
원시 재귀 함수 $\subsetneq$ 전재귀 함수: 아커만 함수는 전재귀이지만 원시 재귀가 아니다.
전재귀 함수 $\subsetneq$ 부분 재귀 함수: 부분 재귀 함수 중 일부 입력에서 정의되지 않는(비정지) 함수가 존재한다.

4. 괴델의 기여의 학문사적 의의

괴델의 재귀 함수 연구는 다음의 의의를 갖는다.

첫째, 불완전성 정리의 증명에서 원시 재귀 함수가 핵심 도구로 사용됨으로써, 재귀 함수의 이론적 중요성이 확립되었다.

둘째, 일반 재귀 함수의 개념 제시가 “효과적 계산 가능성“의 형식화를 향한 핵심 단계를 구성하였다.

셋째, 괴델이 처치의 형식화에 대해 처음에는 유보적 태도를 취하였으나 튜링의 분석 이후 확신하게 된 과정은, 형식적 정의의 직관적 정당화가 수학적 개념 확립에서 갖는 중요성을 보여준다.