4.19 튜링 기계, 람다 대수, 재귀 함수 간의 동치성 증명

1. 세 모델의 동치성

계산 이론의 가장 중요한 결과 중 하나는 튜링 기계(Turing Machine), 람다 대수(Lambda Calculus), 재귀 함수(Recursive Function)라는 세 가지 독립적 계산 모델이 동일한 함수 클래스를 정의한다는 것이다.

$\text{튜링 계산 가능 함수} = \text{람다 정의 가능 함수} = \text{부분 재귀 함수}$

이 동치성은 1936년에 처치(Church), 튜링(Turing), 클레이니(Kleene)에 의해 증명되었다.

동치성의 증명 구조

세 모델의 동치성은 순환적 함의(Cyclic Implication)에 의해 증명된다:

$\text{재귀 함수} \subseteq \text{람다 정의 가능} \subseteq \text{튜링 계산 가능} \subseteq \text{재귀 함수}$

각 포함 관계를 증명하면 세 클래스의 동치성이 확립된다.

2. 재귀 함수 ⊆ 람다 정의 가능 함수

2.1 증명의 개요 (클레이니, 1936)

모든 부분 재귀 함수가 람다 정의 가능함을 보이기 위해, 재귀 함수의 각 구성 단계가 람다 대수에서 표현 가능함을 증명한다.

기초 함수의 람다 표현:

영 함수: $Z = \lambda x. \overline{0}$
후자 함수: $\text{SUCC} = \lambda n. \lambda f. \lambda x. f \; (n \; f \; x)$
사영 함수: $P_i^n = \lambda x_1. \cdots \lambda x_n. x_i$

합성의 람다 표현: $g$ 와 $h_1, \ldots, h_k$ 가 람다 정의 가능하면, $f(\vec{x}) = g(h_1(\vec{x}), \ldots, h_k(\vec{x}))$ 도 람다 정의 가능하다:

$F = \lambda \vec{x}. G \; (H_1 \; \vec{x}) \; \cdots \; (H_k \; \vec{x})$

원시 재귀의 람다 표현: 원시 재귀로 정의된 함수는 처치 수의 반복 적용에 의해 람다 정의 가능하다. $\overline{y} \; h \; g$ 는 $h$ 를 $y$ 번 반복 적용하는 것이며, 이는 원시 재귀의 $y$ -단계 계산에 대응한다.

최소화의 람다 표현: Y 조합자에 의한 재귀를 사용하여, $\mu y [g(\vec{x}, y) = 0]$ 을 $y = 0$ 부터 순차적으로 탐색하는 재귀 함수로 표현한다.

람다 정의 가능 함수 ⊆ 튜링 계산 가능 함수

증명의 개요 (튜링, 1936)

모든 람다 정의 가능 함수가 튜링 기계에 의해 계산 가능함을 보이기 위해, 람다 항의 베타 축약(Beta Reduction)을 수행하는 튜링 기계를 구성한다.

단계 1: 람다 항의 부호화

람다 항을 튜링 기계의 테이프에 기록 가능한 문자열로 부호화한다. 변수, 추상화( $\lambda$ ), 적용을 지정된 기호로 인코딩한다.

단계 2: 베타 축약의 기계적 수행

튜링 기계가 테이프에 기록된 람다 항에서 베타 레덱스를 탐색하고, 대입 연산을 수행하는 절차를 구현한다. 이 절차는 다음을 포함한다:

레덱스 탐색(좌단 최외곽 또는 다른 전략에 따라)
대입 수행(변수 포획 방지를 위한 알파 변환 포함)
축약 결과의 테이프 기록

단계 3: 정규형 판별

베타 레덱스가 더 이상 존재하지 않으면(정규형에 도달하면) 축약을 종료하고, 정규형에 인코딩된 처치 수를 자연수로 복호화한다.

튜링 계산 가능 함수 ⊆ 재귀 함수

증명의 개요

모든 튜링 계산 가능 함수가 부분 재귀적임을 보이기 위해, 튜링 기계의 계산 과정을 재귀 함수로 인코딩한다.

단계 1: 배치의 산술적 부호화

튜링 기계의 배치(Configuration)—상태, 테이프 내용, 헤드 위치—를 자연수로 부호화한다. 괴델 수 기법 또는 쌍 부호화(Pairing Function)를 사용한다.

칸토어의 쌍 함수(Cantor Pairing Function):

$\pi(x, y) = \frac{(x + y)(x + y + 1)}{2} + x$

이 함수는 $\mathbb{N}^2 \rightarrow \mathbb{N}$ 의 전단사(Bijection)이며, 원시 재귀적이다. 역함수 $\pi_1, \pi_2$ 도 원시 재귀적이다.

단계 2: 전이 함수의 산술적 표현

튜링 기계의 전이 함수 $\delta$ 를 산술적 함수로 표현한다. 배치 $c$ 에 대한 한 단계 전이를 수행하는 함수 $\text{next}(c)$ 를 원시 재귀 함수로 정의한다.

단계 3: $t$ -단계 계산의 표현

초기 배치 $c_0$ 에서 $t$ 단계 후의 배치 $c_t$ 를 계산하는 함수를 원시 재귀로 정의한다:

$\text{config}(c_0, 0) = c_0$
$\text{config}(c_0, t+1) = \text{next}(\text{config}(c_0, t))$

단계 4: 정지 조건의 탐색

입력 $\vec{x}$ 에 대해 튜링 기계가 정지하는 최소 단계 $t$ 를 최소화 연산자로 찾는다:

$t^* = \mu t \, [\text{halted}(\text{config}(c_0(\vec{x}), t)) = 0]$

여기서 $\text{halted}(c)$ 는 배치 $c$ 가 정지 배치인지를 판별하는 원시 재귀 함수이다.

단계 5: 출력의 추출

정지 배치에서 출력 값을 추출하는 원시 재귀 함수를 적용한다.

전체 함수:

$f(\vec{x}) = \text{output}(\text{config}(c_0(\vec{x}), \mu t \, [\text{halted}(\text{config}(c_0(\vec{x}), t)) = 0]))$

이 함수는 기초 함수, 합성, 원시 재귀, 최소화에 의해 구성되므로 부분 재귀 함수이다.

3. 동치성의 의의

3.1 처치-튜링 명제의 근거

세 독립적 형식화의 동치성은 처치-튜링 명제의 가장 강력한 근거이다. 외형적으로 완전히 상이한 세 모델—기계적 장치(튜링 기계), 함수적 추상화(람다 대수), 수학적 함수 클래스(재귀 함수)—이 동일한 계산 능력을 갖는다는 사실은, 이 계산 능력이 모델의 구체적 형태에 의존하지 않는 본질적(Intrinsic) 개념임을 시사한다.

3.2 강건성(Robustness)

이후 제안된 모든 합리적 계산 모델—레지스터 기계, 마르코프 알고리즘, 포스트 생산 체계, 셀룰러 오토마타, 타일링 체계 등—이 동일한 함수 클래스를 정의함이 확인되었다. 이 강건성은 “계산 가능성“이 특정 모델에 의존하지 않는 수학적 불변량(Invariant)임을 강력하게 지지한다.

3.3 컴퓨터 과학의 기반

동치성은 이론적 결과(예: 결정 불가능성)가 특정 계산 모델에 한정되지 않고 모든 계산 모델에 보편적으로 적용됨을 보장한다. 튜링 기계에서 증명된 결정 불가능성은 프로그래밍 언어, 람다 대수, 재귀 함수 어디에서도 동일하게 성립한다.