1.21 논리 연산에서 계산 이론으로의 전환: 역사적 맥락

1. 전환의 지적 배경

논리 연산(Logical Operation)에서 계산 이론(Theory of Computation)으로의 전환은 19세기 후반에서 20세기 전반에 걸쳐 진행된 수리논리학의 발전이 도달한 자연스러운 귀결이다. 라이프니츠의 추론 계산법, 불의 논리 대수, 프레게의 술어 논리, 러셀-화이트헤드의 형식 체계, 힐베르트의 형식주의를 관통하는 핵심 아이디어—추론의 기계적 수행 가능성—는 “기계적“이라는 개념 자체의 엄밀한 정의를 요구하였다. 이 요구에 대한 응답이 계산 이론의 탄생이다.

2. 힐베르트의 판정 문제(Entscheidungsproblem)

논리 연산에서 계산 이론으로의 전환을 직접적으로 촉발한 문제는 힐베르트와 아커만(Wilhelm Ackermann)이 1928년 “Grundzüge der theoretischen Logik(이론 논리학의 기초)“에서 명시적으로 정식화한 판정 문제(Entscheidungsproblem)이다.

판정 문제는 다음과 같이 정의된다: 일차 술어 논리의 임의의 문장이 주어졌을 때, 유한한 수의 기계적 단계를 통해 그 문장이 논리적으로 타당한지(Valid) 여부를 판정하는 일반적 절차가 존재하는가?

이 문제에 답하기 위해서는 “유한한 수의 기계적 단계“라는 표현의 정밀한 수학적 정의가 필수적이었다. “기계적 절차“란 정확히 무엇인가? 이 질문에 대한 답변이 계산 가능성(Computability)의 개념이며, 이 개념의 엄밀한 정의가 계산 이론의 출발점이다.

3. 년대의 계산 모델

판정 문제에 대한 답변을 추구하는 과정에서, 1930년대에 여러 독립적인 계산 모델이 거의 동시에 제안되었다.

3.1 괴델의 재귀 함수(Recursive Functions, 1931)

괴델은 불완전성 정리의 증명 과정에서 원시 재귀 함수(Primitive Recursive Function)의 개념을 사용하였다. 이후 헤르브란트(Jacques Herbrand)와 괴델의 논의를 기반으로, 일반 재귀 함수(General Recursive Function)의 개념이 정립되었다.

3.2 처치의 람다 계산(Lambda Calculus, 1936)

알론조 처치(Alonzo Church)는 1936년 “An Unsolvable Problem of Elementary Number Theory“에서 람다 계산(Lambda Calculus)을 제안하였다. 람다 계산은 함수의 정의와 적용만으로 구성되는 순수 함수적 계산 모델이다. 처치는 이 모델을 사용하여 판정 문제가 해결 불가능함을 최초로 증명하였다.

3.3 튜링의 튜링 기계(Turing Machine, 1936)

앨런 튜링은 1936년 “On Computable Numbers, with an Application to the Entscheidungsproblem“에서 튜링 기계(Turing Machine)를 제안하였다. 튜링 기계는 무한 테이프, 읽기/쓰기 헤드, 유한 상태 제어 장치로 구성되는 추상적 계산 장치이다. 튜링은 이 모델을 사용하여 판정 문제가 해결 불가능함을 독립적으로 증명하였다.

3.4 포스트의 생산 체계(Post Production System, 1936)

에밀 포스트(Emil Post)는 1936년 문자열 재작성 규칙(String Rewriting Rules)에 기반한 계산 모델을 제안하였다.

4. 처치-튜링 논제(Church-Turing Thesis)

이 네 가지 독립적 계산 모델이 정의하는 “계산 가능한 함수“의 클래스가 모두 동일하다는 것이 증명되었다. 이 놀라운 수렴은 처치-튜링 논제(Church-Turing Thesis)의 근거가 된다: 직관적으로 “기계적으로 계산 가능한” 함수의 클래스는 재귀 함수(또는 동등하게, 튜링 기계에 의해 계산 가능한 함수, 람다 계산으로 정의 가능한 함수)의 클래스와 일치한다.

처치-튜링 논제는 수학적 정리가 아니라 경험적 가설이다. “직관적으로 기계적으로 계산 가능하다“는 비형식적 개념을 형식적 개념과 동일시하는 것이므로, 수학적 증명의 대상이 아니다. 그러나 이후 제안된 모든 합리적 계산 모델이 튜링 기계와 동등한 계산 능력을 갖는다는 사실은 이 논제에 강력한 경험적 지지를 제공한다.

5. 전환의 의의

논리 연산에서 계산 이론으로의 전환은 다음의 학문사적 의의를 갖는다.

첫째, “계산“의 엄밀한 정의가 확립되었다. 라이프니츠 이래 “기계적 추론” 또는 “기계적 계산“이라는 개념은 직관적으로만 이해되었으나, 1936년의 성과에 의해 이 개념이 수학적으로 정밀하게 정의되었다.

둘째, 계산의 한계가 확정되었다. 모든 수학적 문제가 기계적으로 해결 가능한 것은 아니라는 부정적 결과는, 역설적으로 계산이라는 개념의 본질적 특성을 밝혀주었다. 정지 문제(Halting Problem)의 결정 불가능성은 계산의 근본적 한계를 보여주는 대표적 결과이다.

셋째, 컴퓨터 과학의 이론적 기초가 확립되었다. 튜링 기계는 현대 컴퓨터의 이론적 모델이며, 계산 복잡도 이론(Computational Complexity Theory), 형식 언어 이론(Formal Language Theory), 알고리즘 설계 및 분석의 기반이 된다.

넷째, 인공지능의 이론적 가능성과 한계가 규정되었다. 계산 가능성 이론은 기계에 의한 지능적 행동의 수학적 가능 범위를 규정한다. 기호주의 인공지능의 핵심 전제—지능적 행동이 기호의 기계적 조작으로 구현 가능하다—는 형식 체계와 계산 가능성 이론의 틀 안에서 정밀하게 해석된다.

6. 연속적 지적 계보

논리 연산에서 계산 이론으로의 전환은 라이프니츠→불→프레게→러셀→힐베르트→괴델→처치→튜링이라는 연속적 지적 계보의 귀결이다. 각 단계에서 이전 단계의 성과가 다음 단계의 문제를 정의하였으며, 이 과정은 추상적 논리 체계에서 구체적 계산 장치로의 개념적 하강(Conceptual Descent)을 이루었다. 이 하강의 종착점이 현대 디지털 컴퓨터이며, 이 컴퓨터 위에서 구현된 인공지능은 이 장구한 지적 계보의 최신 산물이다.