4.16 μ-재귀 함수(μ-recursive Functions)와 최소화 연산자

1. 원시 재귀 함수의 한계

원시 재귀 함수(Primitive Recursive Function)는 모든 입력에 대해 정의되는 전역 함수(Total Function)이며, 이로 인해 계산 가능 함수의 전체 클래스를 포괄하지 못한다. 아커만 함수(Ackermann Function)는 계산 가능하지만 원시 재귀적이지 않은 함수의 대표적 예이다.

이 한계를 극복하기 위해 원시 재귀에 무한화 연산자(μ-Operator, Minimization Operator)를 추가한 확장이 μ-재귀 함수(μ-Recursive Function)이다. μ-재귀 함수의 클래스는 튜링 기계에 의해 계산 가능한 함수의 클래스와 정확히 일치한다.

2. 최소화 연산자(μ-Operator)의 정의

2.1 무제한 최소화(Unbounded Minimization)

g: \mathbb{N}^{n+1} \rightarrow \mathbb{N}가 (n+1)-항 함수일 때, 최소화 연산자 \mu에 의해 정의되는 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“를 의미한다.

정밀한 정의

f(\vec{x}) = \mu y \, [g(\vec{x}, y) = 0]은 다음과 같이 정의된다:

f(\vec{x}) = y인 것은 다음 두 조건이 동시에 만족��� 때이다:

1. g(\vec{x}, y) = 0
2. 모든 z < y에 대해 g(\vec{x}, z)가 정의되고 g(\vec{x}, z) \neq 0

만약 이러한 y가 존재하지 않으면, f(\vec{x})는 정의되지 않는다(Undefined). 즉, f는 부분 함수(Partial Function)가 될 수 있다.

정규 최소화(Regular Minimization)

g(\vec{x}, y)가 모든 \vec{x}에 대해 g(\vec{x}, y) = 0인 y가 존재하는 것이 보장되면, 이를 정규 최소화(Regular Minimization)라 하며, 결과 함수 f�� 전역 함수이다.

μ-재귀 함수의 형식적 정의

μ-재귀 함수(또는 부분 재귀 함수, Partial Recursive Function)의 클래스는 다음의 네 가지 구성 요소에 의해 생성되는 함수의 클래스이다:

1. 기초 함수: 영 함수 Z, 후자 함수 S, 사영 함수 P_i^n
2. 합성(Composition): 기존 μ-재귀 함수의 합성
3. 원시 재귀(Primitive Recursion): 원시 재귀에 의한 함수 정의
4. 최소화(μ-Operator): 무제한 최소화에 의한 함수 정의

전재귀 함수(Total Recursive Function)는 모든 입력에 대해 정의된 μ-재귀 함수이다. 부분 재귀 함수는 일부 입력에서 ���의되지 않을 수 있는 μ-재귀 함수이다.

함수 클래스의 계층

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

각 포함이 엄격함:

• 덧셈은 원시 재��이지만 기초 함수가 아니다.
• 아커만 함수는 전재귀이지만 원시 재귀가 아니다.
• 부분 재귀 함수 중 일부 입력에서 정의되지 않는 함수가 존재한다.

3. 최소화 연산자의 계산적 해석

3.1 무한 탐색으로서의 μ-연산자

\mu y \, [g(\vec{x}, y) = 0]의 계산은 다음의 절차에 의해 수행된다:

1. y = 0에서 시작한다.
2. g(\vec{x}, y)를 계산한다.
3. g(\vec{x}, y) = 0이면 y를 반환하고 종료한다.
4. g(\vec{x}, y) \neq 0이면 y \leftarrow y + 1로 갱신하고 단계 2로 돌아간다.

이 절차는 프로그래밍��� while 루프에 대응한다:

y = 0
while g(x, y) ≠ 0:
    y = y + 1
return y

3.2 비종료의 가능성

while 루프와 마찬가지로, g(\vec{x}, y) = 0을 만족하는 y가 존재하지 않으면 탐색은 영원히 계속되며, 함수는 해당 입력에 대해 정의되지 않는다. 이 비종료 가능성이 μ-재귀 함수가 부분 함수가 되는 원인이다.

4. μ-재귀 함수 = 튜링 계산 가능 함수

정리: 부분 함수 f: \mathbb{N}^n \rightharpoonup \mathbb{N}가 μ-재귀적인 것과 튜링 기계에 의해 계산 가능한 것은 동치이다.

이 동치성은 두 방향의 시뮬레이션에 의해 증명된다.

4.1 μ-재귀 → 튜링 계산 가능

μ-재귀 함수의 각 구성 연산(기초 함수, 합성, 원시 재귀, 최소화)이 튜링 기계에 의해 구현 가능함을 보인다. 기초 함수는 자명하게 튜링 계산 가능하고, 합성과 원시 재귀는 서브루틴 호출로, 최소화는 while 루프로 구현된다.

4.2 튜링 계산 가능 → μ-재귀

튜링 기계의 계산 과정을 μ-재귀 함수로 인코딩한다. 튜링 기계의 배치(Configuration)를 자연수로 부호화하고, 전이 함수에 의한 배치 전이를 원시 재귀 함수로 표현하며, 정지 조건의 탐색을 최소화 연산자로 표현한다.

5. 구체적 예시

5.1 제곱근 함수의 μ-재귀적 정의

정수 제��근(Integer Square Root) \text{isqrt}(x) = \lfloor \sqrt{x} \rfloor:

\text{isqrt}(x) = \mu y \, [(y+1)^2 > x] = \mu y \, [\text{monus}((y+1) \times (y+1), x+1) = 0 \text{ is false}]

보다 정확하게:

\text{isqrt}(x) = \mu y \, [\text{sg}(\text{monus}((y+1) \times (y+1), x+1)) = 0]

여기서 \text{sg}는 부호 함수(0이면 0, 양수이면 1)이다. (y+1)^2 > x를 만족하는 가장 ���은 y가 \lfloor \sqrt{x} \rfloor이다.

5.2 정지 함수의 μ-재귀적 비표현 가능성

정지 함수 h(n, m) = 1 if M_n halts on m, = 0 otherwise는 μ-재귀적이지 않다. 이는 정지 문제의 결정 불가능성의 재귀 함수 이론적 표현이다.

6. μ-연산자와 for vs while의 대응

원시 재귀가 for 루프에 대응하고 μ-연산자가 while 루프에 대응한다��� 관찰은, 프로그래밍 언어의 제어 흐름 구조와 재귀 함수 이론 사이의 깊은 연관을 보여준다. while 루프의 추가가 for 루프만으로는 표현 불가능한 계산을 가능하게 하며, 동시에 비종료의 위험을 도입한다.

7. μ-재귀 함수의 이론적 의의

μ-재귀 함수의 클래스가 튜링 계산 가능 함수의 클래스와 일치한다는 동치 정리는 처치-튜링 명제(Church-Turing Thesis)의 핵심적 근거이다. 이 동치성은 “효과적으로 계산 가능한 함수“의 형식적 정의가 특정 형식화 방법에 의존하지 않는 본질적(Intrinsic) 개념임을 보여주며, 이 본질적 개���이 현대 컴퓨터 과학의 이론적 기반을 구성한다.