4.9 람다 대수의 고정점 조합자(Fixed-Point Combinator)

1. 고정점의 수학적 개념

함수 $f$ 의 고정점(Fixed Point)은 $f(x) = x$ 를 만족하는 값 $x$ 이다. 예를 들어, 함수 $f(x) = x^2$ 의 고정점은 $x = 0$ 과 $x = 1$ 이다.

람다 대수에서 고정점의 개념은 함수적으로 확장된다. 람다 항 $F$ 의 고정점은 $F \; X =_\beta X$ 를 만족하는 람다 항 $X$ 이다. 즉, $F$ 를 $X$ 에 적용한 결과가 $X$ 자체와 베타 동치인 것이다.

2. 고정점 정리(Fixed-Point Theorem)

정리: 임의의 람다 항 $F$ 에 대해, $F \; X =_\beta X$ 를 만족하는 람다 항 $X$ 가 존재한다.

이 정리는 순수 람다 대수에서 모든 함수가 고정점을 갖는다는 것을 보장하는 강력한 결과이다. 일반 수학에서 모든 함수가 고정점을 갖는 것은 아니지만(예: $f(x) = x + 1$ ), 유형 없는 람다 대수에서는 자기 적용(Self-Application)의 가능성에 의해 모든 항이 고정점을 갖는다.

3. Y 조합자(Y Combinator)

3.1 정의

처치가 발견한 Y 조합자(Y Combinator)는 다음과 같이 정의된다:

$\mathbf{Y} = \lambda f. (\lambda x. f \; (x \; x)) \; (\lambda x. f \; (x \; x))$

고정점 성질의 증명

임의의 람다 항 $F$ 에 대해 $\mathbf{Y} \; F$ 가 $F$ 의 고정점임을 보인다:

$\mathbf{Y} \; F = (\lambda f. (\lambda x. f \; (x \; x)) \; (\lambda x. f \; (x \; x))) \; F$

베타 축약:

$\rightarrow_\beta (\lambda x. F \; (x \; x)) \; (\lambda x. F \; (x \; x))$

다시 베타 축약:

$\rightarrow_\beta F \; ((\lambda x. F \; (x \; x)) \; (\lambda x. F \; (x \; x)))$

그런데 $(\lambda x. F \; (x \; x)) \; (\lambda x. F \; (x \; x)) = \mathbf{Y} \; F$ 이므로:

$\mathbf{Y} \; F \rightarrow_\beta^* F \; (\mathbf{Y} \; F)$

따라서 $\mathbf{Y} \; F =_\beta F \; (\mathbf{Y} \; F)$ 이며, $\mathbf{Y} \; F$ 는 $F$ 의 고정점이다. $\blacksquare$

튜링 고정점 조합자(Turing Fixed-Point Combinator)

튜링(Alan Turing)이 발견한 다른 고정점 조합자 $\Theta$ :

$\mathbf{A} = \lambda x. \lambda y. y \; (x \; x \; y)$
$\Theta = \mathbf{A} \; \mathbf{A} = (\lambda x. \lambda y. y \; (x \; x \; y)) \; (\lambda x. \lambda y. y \; (x \; x \; y))$

$\Theta$ 의 성질: $\Theta \; F \rightarrow_\beta F \; (\Theta \; F)$

Y 조합자와 달리, $\Theta$ 는 베타 축약(한 방향)에 의해 고정점 성질을 만족한다( $\rightarrow_\beta$ , $=_\beta$ 가 아닌).

고정점 조합자에 의한 재귀의 구현

재귀의 문제

순수 람다 대수에는 자기 참조(Self-Reference)를 위한 내장 메커니즘이 없다. 함수 정의에서 함수 자기 자신을 호출하는 재귀(Recursion)를 직접 표현할 수 없다. 예를 들어, 팩토리얼 함수 $n! = n \times (n-1)!$ 에서 정의 자체가 팩토리얼을 참조한다.

고정점 조합자에 의한 해결

고정점 조합자를 사용하면 재귀를 명시적 자기 참조 없이 구현할 수 있다.

팩토리얼의 “비재귀적 골격“을 먼저 정의한다:

$G = \lambda f. \lambda n. \text{if } (n = 0) \; 1 \; (n \times f \; (n - 1))$

$G$ 는 “재귀적 함수 $f$ 가 주어지면, $n$ 이 0일 때 1을 반환하고, 아닐 때 $n \times f(n-1)$ 을 반환하는 함수“이다. $G$ 는 재귀적이지 않으며, $f$ 를 매개변수로 받는 고차 함수이다.

이제 $\mathbf{Y} \; G$ 를 계산하면:

$\mathbf{Y} \; G =_\beta G \; (\mathbf{Y} \; G)$

$\mathbf{Y} \; G$ 를 $\text{fact}$ 로 놓으면:

$\text{fact} = G \; \text{fact} = \lambda n. \text{if } (n = 0) \; 1 \; (n \times \text{fact} \; (n - 1))$

이는 정확히 팩토리얼의 재귀적 정의이다. 고정점 조합자 $\mathbf{Y}$ 가 $G$ 의 고정점을 구성함으로써, 명시적 자기 참조 없이 재귀를 실현한다.

4. 고정점 조합자의 다양성

고정점 조합자는 유일하지 않으며, 무한히 많은 고정점 조합자가 존재한다. 몇 가지 예:

$\mathbf{Y} = \lambda f. (\lambda x. f \; (x \; x)) \; (\lambda x. f \; (x \; x))$ (처치)
$\Theta = (\lambda x. \lambda y. y \; (x \; x \; y)) \; (\lambda x. \lambda y. y \; (x \; x \; y))$ (튜링)
$\mathbf{Y}_k = (\lambda x. x \; x) \; (\lambda x. \lambda f. f \; (x \; x \; f))$ (클레이니)

모든 고정점 조합자 $\mathbf{Z}$ 는 $\mathbf{Z} \; F =_\beta F \; (\mathbf{Z} \; F)$ 를 만족한다.

5. 적용 순서 Y 조합자(Z Combinator)

적용 순서 평가(Applicative Order Evaluation, Call by Value)를 사용하는 프로그래밍 언어에서 표준 Y 조합자는 비종료를 초래할 수 있다. 이를 해결하기 위해 Z 조합자가 사용된다:

$\mathbf{Z} = \lambda f. (\lambda x. f \; (\lambda v. x \; x \; v)) \; (\lambda x. f \; (\lambda v. x \; x \; v))$

Z 조합자는 에타 확장을 통해 인자의 즉시 평가를 지연(Delay)시킨다.

고정점 조합자의 이론적 의의

고정점 조합자의 존재는 다음의 이론적 함의를 갖는다:

첫째, 재귀의 비원시성(Non-Primitivity): 재귀는 람다 대수의 기본 연산(변수, 추상화, 적용)에 의해 파생 가능한(Derivable) 개념이며, 별도의 원시 연산으로 도입할 필요가 없다.

둘째, 튜링 완전성의 확보: 고정점 조합자에 의한 재귀의 구현 가능성은 람다 대수의 튜링 완전성을 확보하는 핵심 요소이다. 재귀 없이는 임의의 계산 가능 함수를 표현할 수 없다.

셋째, 자기 참조의 형식화: 고정점 조합자는 자기 참조(Self-Reference)를 명시적 이름 참조 없이 구현하는 기제이며, 이는 괴델의 자기 참조적 문장 구성, 폰 노이만의 자기 복제 오토마타, 그리고 컴퓨터 바이러스의 구성과 구조적으로 동형이다.

고정점 조합자는 람다 대수의 표현력의 핵심 요소이며, 재귀적 계산의 형식적 기반을 제공하는 근본적 이론적 도구이다.