4.15 원시 재귀 함수(Primitive Recursive Functions)의 정의와 구성

1. 원시 재귀 함수의 역사적 배경

원시 재귀 함수(Primitive Recursive Function)의 개념은 데데킨트(Richard Dedekind)가 1888년 “Was sind und was sollen die Zahlen?“에서 자연수 위의 함수를 재귀적으로 정의하는 방법을 체계화한 데서 기원한다. 괴델(Kurt Gödel)은 1931년 불완전성 정리의 증명에서 이 개념을 핵심적으로 사용하였으며, 형식 체계의 구문론적 성질을 산술적으로 분석하는 괴델 수 기법(Gödel Numbering)이 원시 재귀 함수에 의해 수행됨을 보였다.

2. 기초 함수(Initial Functions)

원시 재귀 함수의 구성을 위한 세 가지 기초 함수를 정의한다.

2.1 영 함수(Zero Function)

$Z: \mathbb{N} \rightarrow \mathbb{N}, \quad Z(x) = 0$

모든 입력에 대해 0을 반환하는 상수 함수이다. $n$ -항 영 함수 $Z^n(x_1, \ldots, x_n) = 0$ 으로 일반화된다.

후자 함수(Successor Function)

$S: \mathbb{N} \rightarrow \mathbb{N}, \quad S(x) = x + 1$

입력에 1을 더한 값을 반환한다. 페아노 공리(Peano Axioms)에서 자연수 체계를 생성하는 기본 연산이다.

2.2 사영 함수(Projection Function)

$P_i^n: \mathbb{N}^n \rightarrow \mathbb{N}, \quad P_i^n(x_1, x_2, \ldots, x_n) = x_i \quad (1 \leq i \leq n)$

$n$ 개의 인자 중 $i$ 번째 인자를 반환하는 함수이다. $n$ 과 $i$ 의 각 조합에 대해 하나의 사영 함수가 정의된다.

구성 연산(Construction Operations)

기초 함수로부터 새로운 원시 재귀 함수를 구성하는 두 가지 연산이다.

합성(Composition)

$g: \mathbb{N}^k \rightarrow \mathbb{N}$ 가 $k$ -항 원시 재귀 함수이고, $h_1, h_2, \ldots, h_k: \mathbb{N}^n \rightarrow \mathbb{N}$ 가 각각 $n$ -항 원시 재귀 함수이면, 합성에 의해 정의되는 $f: \mathbb{N}^n \rightarrow \mathbb{N}$ :

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

은 원시 재귀 함수이다.

합성은 함수의 출력을 다른 함수의 입력으로 연결하는 연산이며, 프로그래밍에서의 함수 합성(Function Composition)에 직접 대응한다.

2.3 원시 재귀(Primitive Recursion)

$g: \mathbb{N}^n \rightarrow \mathbb{N}$ 가 $n$ -항 원시 재귀 함수이고, $h: \mathbb{N}^{n+2} \rightarrow \mathbb{N}$ 가 $(n+2)$ -항 원시 재귀 함수이면, 원시 재귀에 의해 정의되는 $f: \mathbb{N}^{n+1} \rightarrow \mathbb{N}$ :

$f(\vec{x}, 0) = g(\vec{x})$
$f(\vec{x}, y+1) = h(\vec{x}, y, f(\vec{x}, y))$

은 원시 재귀 함수이다. 여기서 $\vec{x} = (x_1, \ldots, x_n)$ 이다.

원시 재귀의 구조:

기저 단계(Base Case): $y = 0$ 일 때 함수값은 $g(\vec{x})$ 로 결정된다.
재귀 단계(Recursive Step): $y+1$ 에서의 함수값은 $\vec{x}$ , 이전 인덱스 $y$ , 그리고 이전 함수값 $f(\vec{x}, y)$ 에 의해 결정된다.

원시 재귀는 프로그래밍에서의 for 루프에 대응한다. 반복 횟수가 인자 $y$ 에 의해 미리 결정되며, 각 반복에서 이전 결과를 사용하여 다음 결과를 계산한다.

3. 원시 재귀 함수의 구성 예시

3.1 덧셈(Addition)

$\text{add}: \mathbb{N}^2 \rightarrow \mathbb{N}$

$\text{add}(x, 0) = P_1^1(x) = x$
$\text{add}(x, y+1) = S(P_3^3(x, y, \text{add}(x, y))) = S(\text{add}(x, y))$

즉, $g = P_1^1$ (항등), $h(x, y, z) = S(z) = z + 1$ .

검증: $\text{add}(3, 2) = S(\text{add}(3, 1)) = S(S(\text{add}(3, 0))) = S(S(3)) = S(4) = 5$ ✓

3.2 곱셈(Multiplication)

$\text{mult}: \mathbb{N}^2 \rightarrow \mathbb{N}$

$\text{mult}(x, 0) = Z(x) = 0$
$\text{mult}(x, y+1) = \text{add}(x, \text{mult}(x, y))$

$g = Z$ , $h(x, y, z) = \text{add}(x, z)$ .

3.3 거듭제곱(Exponentiation)

$\text{exp}(x, 0) = S(Z(x)) = 1$
$\text{exp}(x, y+1) = \text{mult}(x, \text{exp}(x, y))$

3.4 선행자(Predecessor)

$\text{pred}(0) = 0$
$\text{pred}(y+1) = P_1^2(y, \text{pred}(y)) = y$

3.5 제한 뺄셈(Modified Subtraction, Monus)

$\text{monus}(x, 0) = x$
$\text{monus}(x, y+1) = \text{pred}(\text{monus}(x, y))$

$\text{monus}(a, b) = \max(a - b, 0)$

3.6 부호 함수(Signum)

$\text{sg}(0) = 0, \quad \text{sg}(y+1) = 1$

제한 양화(Bounded Quantification)

원시 재귀 함수에 의해 정의된 술어 $P(\vec{x}, y)$ 에 대해, 제한 양화:

$(\exists y \leq z) \; P(\vec{x}, y) \quad \text{및} \quad (\forall y \leq z) \; P(\vec{x}, y)$

는 원시 재귀적이다. 이는 제한된 범위 내에서의 탐색이 원시 재귀로 구현 가능함을 의미한다.

3.7 제한 무한화(Bounded Minimization)

$\mu y \leq z \; [P(\vec{x}, y)]$

$z$ 이하에서 $P$ 를 만족하는 가장 작은 $y$ 를 반환하며, 존재하지 않으면 $z+1$ 을 반환한다. 제한 무한화도 원시 재귀적이다.

원시 재귀 함수의 폐포 성질

원시 재귀 함수의 클래스는 다음의 연산에 대해 폐쇄적(Closed)이다:

기초 함수의 포함
합성에 대한 폐쇄
원시 재귀에 대한 폐쇄
경우 나누기(Case Analysis)에 대한 폐쇄
제한 양화에 대한 폐쇄
제한 무한화에 대한 폐쇄

이 폐포 성질은 원시 재귀 함수의 클래스가 광범위한 수학적 함수를 포함함을 보장한다. 실용적으로 접하는 대부분의 계산 가능 함수—사칙연산, 소수 판별, 최대공약수, 이항 계수 등—는 원시 재귀적이다.

원시 재귀 함수의 전역성

원시 재귀 함수의 핵심적 성질은 전역성(Totality)이다. 모든 원시 재귀 함수는 모든 입력에 대해 정의되며(즉, 항상 정지하며), 값을 산출한다. 이는 원시 재귀의 구조에서 재귀 깊이가 인자에 의해 유계(Bounded)이기 때문이다. for 루프가 항상 종료하듯이, 원시 재귀로 정의된 함수는 항상 종료한다.

이 전역성은 원시 재귀 함수의 중요한 장점이지만, 동시에 한계의 원인이기도 하다. 아커만 함수(Ackermann Function)와 같이, 재귀 깊이가 입력에 의해 유계되지 않는 함수는 원시 재귀적이지 않다.

원시 재귀 함수와 괴델의 불완전성 정리

괴델은 불완전성 정리의 증명에서 형식 체계의 구문론적 성질—공리인가, 증명인가, 증명 가능한가 등—을 원시 재귀 함수로 표현하였다. 괴델 수 부호화(Gödel Numbering)에 의해 형식적 표현이 자연수로 변환되고, 구문론적 관계가 원시 재귀 관계로 표현된다. 이 산술화(Arithmetization)가 형식 체계의 자기 참조적 문장 구성을 가능하게 하는 핵심 기제이다.