Chapter 4. 처치-튜링 명제와 계산 가능성 이론의 성립

1. 계산 가능성 이론의 탄생

계산 가능성 이론(Computability Theory)은 “무엇이 기계적으로 계산 가능한가?“라는 근본적 물음에 대한 수학적 답변을 제공하는 이론이다. 이 이론은 1930년대에 괴델(Kurt Gödel), 처치(Alonzo Church), 튜링(Alan Turing), 포스트(Emil Post), 클레이니(Stephen Kleene) 등의 독립적이면서도 수렴적인 연구에 의해 확립되었다.

핵심 성과는 “효과적으로 계산 가능하다“라는 직관적 개념을 수학적으로 정밀하게 정의한 것이며, 여러 독립적 형식화가 모두 동일한 함수 클래스를 결정한다는 발견이다. 이 수렴이 처치-튜링 명제(Church-Turing Thesis)의 근거이다.

2. 복수의 독립적 형식화

1930년대에 “효과적 계산 가능성“을 위해 상이한 수학적 모델이 독립적으로 제안되었다: 괴델-헤르브란트의 일반 재귀 함수(1934), 처치의 람다 계산(1936), 튜링의 튜링 기계(1936), 포스트의 생산 체계(1936). 이 모델들은 외형적으로 완전히 상이하지만, 정의하는 함수 클래스가 동일함이 증명되었다.

3. 처치-튜링 명제

처치-튜링 명제는 “직관적으로 효과적으로 계산 가능한 함수의 클래스는 재귀 함수(또는 튜링 계산 가능 함수)의 클래스와 일치한다“고 진술한다. 이 명제는 수학적 정리가 아닌 경험적 가설이며, 다수의 독립적 형식화의 수렴과 반례의 부재에 의해 지지된다.

4. 람다 계산(Lambda Calculus)

처치가 1932–1936년에 개발한 람다 계산은 함수의 정의와 적용만으로 구성되는 순수 함수적 계산 모델이다. 람다 계산에서 모든 계산은 람다 항(Lambda Term)의 베타 축약(Beta Reduction)에 의해 수행된다. 람다 계산은 함수형 프로그래밍 언어(Functional Programming Language)의 이론적 기반이다.

5. 재귀 함수 이론

클레이니(Stephen Kleene)는 괴델의 일반 재귀 함수 개념을 체계화하여 재귀 함수 이론을 확립하였다. 원시 재귀 함수(Primitive Recursive Function)는 기본 함수, 합성, 원시 재귀에 의해 정의되며, 뮤 재귀 함수(μ-Recursive Function)는 무한화 연산자를 추가하여 튜링 계산 가능 함수 전체를 포착한다.

6. 클레이니의 정규형 정리

클레이니의 정규형 정리(Kleene’s Normal Form Theorem)는 모든 부분 재귀 함수가 원시 재귀 함수와 무한화 연산자의 단일 적용으로 표현 가능함을 보장한다. 이 정리는 재귀 함수의 구조적 분석을 위한 핵심 도구이다.

7. 재귀 정리(Recursion Theorem)

클레이니의 재귀 정리는 모든 튜링 기계에 대해 자기 자신의 부호화에 접근할 수 있는 동등한 기계가 존재함을 보장한다. 이 정리는 자기 복제 프로그램(Quine), 컴퓨터 바이러스의 존재 가능성, 괴델 문장의 구성에서 핵심적으로 사용된다.

8. 환원과 결정 불가능성

문제 A에서 문제 B로의 환원(Reduction)은 A의 해결을 B의 해결로 변환하는 효과적 절차이다. 환원에 의해 결정 불가능성이 전이되며, 정지 문제로부터 다수의 결정 불가능성 결과가 도출된다.

9. 라이스의 정리(Rice’s Theorem)

라이스의 정리는 튜링 기계가 계산하는 함수에 관한 모든 비자명(Nontrivial) 성질이 결정 불가능함을 보장한다. 이 정리는 프로그램 분석의 근본적 한계를 규정하며, 완벽한 자동 프로그램 검증기의 불가능성을 함의한다.

10. 인공지능에 대한 함의

계산 가능성 이론은 인공지능의 원리적 가능성과 한계를 동시에 규정한다. 처치-튜링 명제가 정확하고 인간 지능이 알고리즘적 과정이라면, 인간 지능은 원리적으로 기계에 의해 시뮬레이션 가능하다. 동시에, 결정 불가능성 결과는 어떤 인공지능 체계도 일반적으로 해결할 수 없는 문제의 존재를 확정한다. 이 두 측면의 긴장이 인공지능의 이론적 탐구를 특징짓는다.