3.2 결정 문제의 역사적 기원과 힐베르트의 제안
1. 결정 문제의 지적 배경
결정 문제(Entscheidungsproblem)는 수학의 기초론(Foundations of Mathematics) 논쟁의 핵심에서 출현한 문제이다. 이 문제의 역사적 기원은 19세기 후반부터 20세기 초반에 걸쳐 전개된 수학의 엄밀화(Rigorization) 운동과 수학적 방법론에 대한 메타수학적 성찰에 있다.
2. 라이프니츠의 선행 구상
결정 문제의 개념적 원형은 라이프니츠(Gottfried Wilhelm Leibniz)의 보편 기호학(Characteristica Universalis)과 추론 계산법(Calculus Ratiocinator) 구상에서 발견된다. 라이프니츠는 모든 학문적 논쟁이 올바른 기호 체계와 추론 규칙의 기계적 적용에 의해 해결될 수 있다고 구상하였다. “계산해 봅시다(Calculemus!)“라는 그의 선언은 임의의 명제의 진위를 기계적 절차에 의해 판정할 수 있다는 이상을 표현한 것이며, 이는 판정 문제의 비형식적 선행 형태이다.
라이프니츠의 구상은 그의 시대에 실현 가능한 수학적 도구가 부재하였기 때문에 프로그램 차원에 머물렀으나, 이후 수리논리학의 발전을 통해 이 구상의 정밀한 수학적 정식화가 가능해졌다.
3. 세기 수리논리학의 발전
3.1 프레게의 형식 체계(1879)
프레게(Gottlob Frege)의 개념 표기법(Begriffsschrift, 1879)은 일차 술어 논리(First-Order Predicate Logic)의 형식적 공리화를 최초로 달성한 저작이다. 프레게의 형식 체계에서 논리적 추론은 명시적 공리와 추론 규칙의 기계적 적용으로 수행된다. 이 형식화의 성공은 수학적 추론의 전 과정이 원리적으로 기계화 가능하다는 전망을 강화하였다.
3.2 러셀과 화이트헤드의 『수학 원리』(1910–1913)
러셀(Bertrand Russell)과 화이트헤드(Alfred North Whitehead)의 『수학 원리(Principia Mathematica)』는 수학의 전 체계를 형식적 공리와 추론 규칙으로부터 연역하는 대규모 프로젝트이다. 이 저작은 형식적 방법론의 위력을 실증하였으며, 수학적 추론의 완전한 기계화라는 목표에 대한 낙관주의를 강화하였다.
4. 힐베르트의 수학 기초론 프로그램
4.1 년 파리 연설
힐베르트(David Hilbert)는 1900년 파리 국제 수학자 대회에서 20세기 수학이 해결해야 할 23가지 문제를 제시하였다. 이 중 제2문제는 산술 공리의 무모순성(Consistency) 증명이었으며, 제10문제는 디오판토스 방정식(Diophantine Equation)의 해 존재를 판정하는 일반적 알고리즘의 존재 여부를 묻는 것이었다. 특히 제10문제는 결정 문제의 특수한 형태이다.
4.2 힐베르트 프로그램(1920년대)
힐베르트 프로그램은 수학의 완전한 형식화, 무모순성 증명, 완전성 증명, 그리고 결정 가능성 확인이라는 네 가지 목표를 추구하였다. 결정 가능성(Decidability)의 확인은 이 프로그램의 네 번째이자 최종적 목표이며, 이것이 판정 문제로 정식화된 것이다.
4.3 년의 명시적 정식화
힐베르트와 아커만(Wilhelm Ackermann)은 1928년 교과서 “Grundzüge der theoretischen Logik“에서 판정 문제를 명시적으로 정식화하였다. 이 교과서에서 판정 문제는 다음과 같이 진술되었다:
일차 술어 논리의 임의의 논리식이 주어졌을 때, 이 논리식이 보편적으로 타당한지(Universally Valid, 즉 모든 해석에서 참인지)를 유한한 수의 단계로 판정하는 절차가 존재하는가?
힐베르트는 이 문제에 대해 긍정적 해답이 가능할 것으로 기대하였다. 그의 유명한 경구 “Wir müssen wissen, wir werden wissen(우리는 알아야 한다, 우리는 알게 될 것이다)“는 수학적 문제의 원리적 해결 가능성에 대한 그의 강한 낙관주의를 표현한다.
5. 괴델의 불완전성 정리와 판정 문제의 관계
괴델의 제1 불완전성 정리(1931)는 판정 문제에 대한 부정적 해답을 강하게 시사하였다. 충분히 강력한 무모순 형식 체계에서 증명도 반증도 불가능한 명제가 존재한다면, 모든 명제의 진위를 기계적으로 판정하는 것은 불가능할 것으로 예상된다.
그러나 괴델의 결과만으로는 판정 문제를 직접 해결할 수 없었다. 판정 문제의 해결에는 “효과적 절차” 또는 “기계적 방법“이라는 개념의 엄밀한 수학적 정의가 필요하였다. 괴델 자신은 이 비형식적 개념의 형식화에 신중한 태도를 취하였으며, 일반 재귀 함수(General Recursive Function)의 개념이 직관적 계산 가능성을 완전히 포착하는지에 대해 확신을 유보하였다.
6. 판정 문제의 해결을 향한 경쟁
1930년대 중반에 여러 수학자가 거의 동시에 “효과적 절차“의 형식적 정의를 제안하고 판정 문제를 해결하였다.
- 처치(Alonzo Church): 1936년 초, 람다 정의 가능성(Lambda Definability)의 개념을 사용하여 판정 문제의 부정적 해결을 최초로 발표하였다.
- 튜링(Alan Turing): 1936년 후반, 튜링 기계를 사용하여 독립적으로 판정 문제의 부정적 해결을 달성하였다. 튜링의 증명은 “효과적 절차“의 개념을 인간 계산자의 분석으로부터 직관적으로 정당화한 점에서 처치의 증명에 비해 개념적 명료성이 높다고 평가된다.
7. 판정 문제 해결의 역사적 의의
판정 문제의 부정적 해결은 힐베르트 프로그램의 최종 목표가 달성 불가능함을 확정하였다. 그러나 이 부정적 결과는 역설적으로 계산 이론(Theory of Computation)이라는 새로운 수학 분야의 탄생을 촉진하였다. “무엇이 계산 가능한가“라는 물음의 부정적 측면—“무엇이 계산 불가능한가”—을 규명하는 과정에서, “계산“이라는 개념 자체가 엄밀한 수학적 대상으로 확립되었다.
결정 문제의 역사적 기원은 라이프니츠의 형이상학적 이상에서 출발하여, 프레게의 형식 논리학, 러셀의 형식 체계, 힐베르트의 메타수학을 거쳐, 튜링과 처치의 계산 이론에 이르는 3세기에 걸친 지적 계보를 형성한다. 이 계보는 인간 사유의 기계화 가능성이라는 근본적 물음의 점진적 정밀화의 과정이며, 이 과정의 귀결이 현대 컴퓨터 과학의 이론적 기초이다.