4.13 처치의 결정 불가능성 증명: 람다 정의 가능성의 한계

1. 처치의 정리의 역사적 맥락

처치(Alonzo Church)는 1936년 “An Unsolvable Problem of Elementary Number Theory“에서 일차 술어 논리의 타당성 문제(Validity Problem)가 결정 불가능(Undecidable)함을 증명하였다. 이 결과는 힐베르트의 판정 문제(Entscheidungsproblem)에 대한 최초의 부정적 해답이며, 처치의 정리(Church’s Theorem)로 알려져 있다.

처치의 증명에 선행하여, 처치는 “효과적 계산 가능성“을 “람다 정의 가능성(Lambda Definability)“으로 형식화하는 것을 제안하였다. 이 형식화가 처치의 명제(Church’s Thesis)의 핵심이다.

2. 처치의 명제(Church’s Thesis)

2.1 진술

함수 f: \mathbb{N} \rightarrow \mathbb{N}가 직관적으로 효과적으로 계산 가능하다면, f는 람다 정의 가능(Lambda Definable)하다.

역으로, 람다 정의 가능한 모든 함수는 직관적으로 효과적으로 계산 가능하다. 따라서 두 개념은 외연적으로 동치이다.

2.2 증거

처치의 명제를 지지하는 증거:

1. 클레이니의 결과(1936): 람다 정의 가능 함수 = 일반 재귀 함수(General Recursive Function). 처치의 제자 클레이니가 이 동치성을 증명하였다.
2. 튜링의 결과(1936): 튜링 계산 가능 함수 = 람다 정의 가능 함수. 튜링이 논문 부록에서 증명하였다.
3. 반례의 부재: 직관적으로 계산 가능하지만 람다 정의 불가능한 함수가 발견된 적이 없다.
4. 다수 형식화의 수렴: 독립적으로 제안된 여러 형식화가 모두 동일한 함수 클래스를 정의한다.

3. 처치의 결정 불가능성 증명

3.1 증명의 구조

처치의 증명은 다음의 단계로 구성된다.

단계 1: 해결 불가능 문제의 존재 확립

클레이니는 1936년 자연수 위의 특정 문제가 일반 재귀 함수에 의해 해결 불가능함을 대각선 논법으로 증명하였다.

모든 단항 재귀 함수를 f_0, f_1, f_2, \ldots로 열거한다(각 f_i는 인덱스 i를 가진 재귀 함수). 다음의 함수 g를 정의한다:

g(n) = f_n(n) + 1

g가 재귀 함수라고 가정하면, g = f_k (어떤 k에 대해)이다. 그러면:

g(k) = f_k(k) + 1 = g(k) + 1

이는 모순이다. 따라서 g는 재귀 함수가 아니다.

더 정밀하게, 다음의 결정 문제가 재귀적으로 해결 불가능함이 증명된다: “인덱스 n의 재귀 함수 f_n이 입력 m에 대해 정의되는가(즉, 정지하는가)?”

단계 2: 환원(Reduction)

단계 1에서 확립된 결정 불가능 문제를 일차 술어 논리의 타당성 문제로 환원한다. 즉, 재귀 함수의 정지 여부를 판별하는 문제를 일차 술어 논리의 문장의 타당성 여부를 판별하는 문제로 변환하는 효과적 절차가 존재함을 보인다.

구체적으로, 재귀 함수 f_n이 입력 m에 대해 값 v를 산출하는 것이 일차 술어 논리의 특정 문장 \Phi_{n,m,v}의 타당성과 동치가 되도록 문장을 구성한다.

단계 3: 결론

일차 술어 논리의 타당성 문제를 결정하는 알고리즘이 존재한다면, 이를 사용하여 재귀 함수의 정지 여부를 결정할 수 있다. 그러나 단계 1에서 후자가 결정 불가능함이 증명되었으므로, 일차 술어 논리의 타당성 문제도 결정 불가능하다.

4. 람다 정의 가능성의 한계

4.1 비계산 가능 함수의 존재

처치의 증명은 람다 정의 불가능한(따라서 효과적으로 계산 불가능한) 함수가 존재함을 확립한다.

\mathbb{N} \rightarrow \mathbb{N} 함수의 집합은 비가산(Uncountable)이다(칸토어의 대각선 논법에 의해). 그러나 람다 항의 집합(따라서 람다 정의 가능 함수의 집합)은 가산(Countable)이다(유한 알파벳 위의 유한 문자열의 집합이므로). 따라서 대부분의 함수 f: \mathbb{N} \rightarrow \mathbb{N}는 람다 정의 불가능하다.

4.2 구체적 비계산 가능 함수

정지 함수: h(n, m) = \begin{cases} 1 & \text{if } f_n(m) \text{ halts} \\ 0 & \text{otherwise} \end{cases}

정지 함수는 람다 정의 불가능(= 재귀적이지 않음 = 튜링 계산 불가능)하다.

비지 비버 함수(Busy Beaver Function): $BB(n) = $ n-상태 튜링 기계 중 빈 테이프에서 시작하여 정지하는 기계가 쓰는 1의 최대 수.

비지 비버 함수는 어떤 재귀 함수보다도 빠르게 성장하며, 계산 불가능하다.

5. 처치의 증명과 튜링의 증명의 비교

처치와 튜링은 독립적으로 판정 문제의 결정 불가능성을 증명하였으나, 접근법이 상이하다.

괴델은 처치의 형식화보다 튜링의 형식화에 대해 더 높은 직관적 확신을 표명하였다. 괴델은 튜링이 인간 계산자의 행동 분석으로부터 기계의 정의를 도출한 점이 “효과적 절차“의 올바른 포착에 대한 결정적 논거를 제공한다고 평가하��다.

6. 결정 불가능성의 파급 효과

처치의 결정 불가능성 증명은 다음의 학문사적 파급 효과를 갖는다.

첫째, 힐베르트 프로그램의 종결: 판정 문제의 부정적 해결은 힐베르트 프로그램의 세 번째이자 마지막 목표(결정 가능성)의 달성 불가능성을 확정하였다. 괴델의 불완전성 정리와 함께, 이 결과는 수학의 형식적 기초에 관한 힐베르트의 낙관주의를 근본적으로 제한하였다.

둘째, 계산 이론의 확립: “효과적 절차“의 형식적 정의와 이를 기반으로 한 결정 불가능성 증명은 계산 이론(Computability Theory)을 독립적 수학 분야로 확립하였다.

셋째, 알고리즘적 한계의 인식: 기계적 방법으로는 원리적으로 해결할 수 없는 문제가 존재한다는 인식은 수학, 컴퓨터 과학, 인공지능 연구의 방법론적 기반에 심대한 영향을 미쳤다.

처치의 결정 불가능성 증명은 “계산 가능한 것“과 “계산 불가능한 것“의 경계를 수학적으로 확정한 역사적 결과이며, 이 경계의 발견이 현대 컴퓨터 과학과 인공지능의 이론적 토대를 구성한다.