4.1 계산 가능성 이론의 역사적 배경과 문제 의식

1. 수학 기초론의 위기

계산 가능성 이론(Computability Theory)의 탄생 배경에는 19세기 말부터 20세기 초까지 전개된 수학 기초론(Foundations of Mathematics)의 위기가 놓여 있다. 칸토어(Georg Cantor)의 집합론에서 발견된 역리(Paradox)—특히 러셀의 역리(Russell’s Paradox, 1901)와 브랄리-포르티의 역리(Burali-Forti Paradox, 1897)—는 수학의 논리적 기초에 대한 근본적 의문을 제기하였다.

이 위기에 대한 대응으로 세 가지 주요 학파가 형성되었다: 러셀의 논리주의(Logicism), 브라우어의 직관주의(Intuitionism), 힐베르트의 형식주의(Formalism). 계산 가능성 이론의 직접적 동기를 제공한 것은 힐베르트의 형식주의 프로그램이다.

2. 힐베르트의 세 가지 물음

힐베르트 프로그램(Hilbert’s Program)은 수학의 형식적 기초에 관해 세 가지 근본적 물음을 제기하였다:

완전성(Completeness): 형식 체계에서 모든 참인 명제가 증명 가능한가?
무모순성(Consistency): 형식 체계에서 모순이 도출되지 않음을 증명할 수 있는가?
결정 가능성(Decidability): 임의의 명제의 증명 가능성을 기계적으로 판정하는 알고리즘이 존재하는가?

이 세 물음에 대한 답변이 계산 가능성 이론의 핵심 결과를 구성한다.

3. 괴델의 불완전성 정리(1931)

괴델은 1931년 “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I“에서 제1 불완전성 정리와 제2 불완전성 정리를 증명하여 힐베르트 프로그램의 처음 두 물음에 대해 부정적 답변을 제공하였다.

제1 불완전성 정리: 페아노 산술을 포함하는 충분히 강력한 무모순 형식 체계에서, 체계 내에서 증명도 반증도 불가능한 참인 문장이 존재한다.

제2 불완전성 정리: 그러한 형식 체계는 자기 자신의 무모순성을 증명할 수 없다.

괴델의 결과는 힐베르트 프로그램의 완전성과 무모순성 목표가 달성 불가능함을 확정하였으나, 세 번째 물음(결정 가능성)에 대해서는 직접적 답변을 제공하지 못하였다.

4. “효과적 절차“의 형식화 필요성

힐베르트의 세 번째 물음—결정 가능성, 즉 판정 문제(Entscheidungsproblem)—에 답하기 위해서는 “효과적 절차(Effective Procedure)” 또는 “기계적 방법(Mechanical Method)“이라는 직관적 개념의 엄밀한 수학적 정의가 선행되어야 하였다. “효과적 절차가 존재하지 않는다“는 부정적 명제를 증명하려면, “효과적 절차“의 범위를 수학적으로 정밀하게 규정해야 하기 때문이다.

이 형식화의 필요성이 계산 가능성 이론 탄생의 직접적 동기이다. 1930년대 중반에 여러 수학자가 이 형식화를 거의 동시에, 그러나 독립적으로 달성하였다.

5. 핵심 인물과 그들의 기여

5.1 괴델(Kurt Gödel, 1906–1978)

원시 재귀 함수(Primitive Recursive Function)의 개념을 불완전성 정리의 증명에서 사용하였으며(1931), 일반 재귀 함수(General Recursive Function)의 개념을 헤르브란트와의 논의에 기반하여 1934년 프린스턴 강의에서 제시하였다. 괴델 자신은 일반 재귀 함수가 직관적 계산 가능성을 완전히 포착하는지에 대해 처음에는 신중한 유보적 태도를 취하였으나, 이후 튜링의 분석에 의해 확신하게 되었다.

5.2 처치(Alonzo Church, 1903–1995)

프린스턴 대학교의 수학 교수로서, 람다 계산(Lambda Calculus)을 개발하고(1932–1936), 이를 사용하여 판정 문제의 결정 불가능성을 최초로 증명하였다(1936). 또한 “효과적 계산 가능성 = 일반 재귀성“이라는 명제를 최초로 명시적으로 제안하였으며, 이 명제가 처치의 명제(Church’s Thesis)로 알려지게 되었다.

5.3 튜링(Alan Turing, 1912–1954)

케임브리지 대학교의 수학자로서, 튜링 기계(Turing Machine)를 도입하고(1936), 이를 사용하여 판정 문제의 결정 불가능성을 독립적으로 증명하였다. 튜링의 독자적 기여는 “효과적 절차“의 개념을 인간 계산자(Human Computer)의 행동 분석으로부터 도출하여, 형식화의 직관적 정당성을 제공한 것이다. 괴델은 튜링의 분석에 의해 비로소 형식적 정의가 직관적 개념을 올바르게 포착한다고 확신하게 되었다.

5.4 클레이니(Stephen Kleene, 1909–1994)

처치의 제자로서, 재귀 함수 이론(Theory of Recursive Functions)을 체계화하고, 정규형 정리(Normal Form Theorem), 재귀 정리(Recursion Theorem) 등 핵심 결과를 증명하였다. 클레이니는 처치의 명제를 “처치의 명제(Church’s Thesis)“로 명명한 최초의 인물이다.

5.5 포스트(Emil Post, 1897–1954)

시립 대학교 뉴욕(City College of New York)의 수학 교수로서, 1936년 독립적으로 튜링 기계와 유사한 계산 모델을 제안하였으며, 1944년 재귀적으로 열거 가능한 집합의 계층 구조를 분석하였다.

6. 문제 의식의 수렴

이 다섯 학자의 연구는 다음의 공통된 문제 의식에서 수렴하였다: “기계적으로 수행 가능한 계산“이라는 직관적 개념을 수학적으로 정밀하게 포착할 수 있는가? 그리고 이 정밀한 정의를 사용하여, 기계적으로 해결 불가능한 문제의 존재를 증명할 수 있는가?

이 물음에 대한 긍정적 답변이 계산 가능성 이론의 확립이며, 이 이론은 현대 컴퓨터 과학과 인공지능의 이론적 토대를 구성한다.