3.1 앨런 튜링의 학문적 배경과 결정 문제(Entscheidungsproblem)

1. 앨런 튜링의 생애와 학문적 형성

앨런 매시슨 튜링(Alan Mathison Turing, 1912–1954)은 영국 런던 메이다 베일(Maida Vale)에서 태어났다. 1931년 케임브리지 대학교(University of Cambridge) 킹스 칼리지(King’s College)에 입학하여 수학을 전공하였으며, 맥스 뉴먼(Max Newman) 교수의 강의에서 괴델의 불완전성 정리와 힐베르트의 판정 문제를 접하게 되었다. 이 경험이 튜링의 학문적 관심을 수학의 기초론과 계산 가능성 이론으로 이끈 직접적 계기가 되었다.

튜링은 1934년 케임브리지에서 학사 학위를 취득한 후, 1935년 킹스 칼리지의 펠로(Fellow)로 선출되었다. 이 시기에 튜링은 계산 가능성(Computability)의 문제를 본격적으로 연구하기 시작하였으며, 그 결과가 1936년의 기념비적 논문이다.

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

2.1 문제의 기원

판정 문제(Entscheidungsproblem, 독일어로 “결정 문제”)는 힐베르트(David Hilbert)와 아커만(Wilhelm Ackermann)이 1928년 저서 “Grundzüge der theoretischen Logik(이론 논리학의 기초)“에서 명시적으로 정식화한 문제이다. 이 문제는 힐베르트 프로그램(Hilbert’s Program)의 핵심 목표 중 하나와 직결된다.

2.2 문제의 정식화

판정 문제는 다음과 같이 정의된다:

일차 술어 논리(First-Order Predicate Logic)의 임의의 폐쇄식(Closed Formula)이 주어졌을 때, 그 식이 논리적으로 타당한지(Valid), 즉 모든 해석(Interpretation)에서 참인지를 판정하는 효과적 절차(Effective Procedure)가 존재하는가?

“효과적 절차“란 유한한 수의 기계적 단계로 구성되며, 각 단계가 명확히 정의되고, 절차가 반드시 종료(Terminate)하는 절차를 의미한다. 현대적 용어로는 알고리즘(Algorithm)에 해당한다.

2.3 문제의 의의

판정 문제가 긍정적으로 해결된다면, 수학의 모든 정리의 증명 가능성이 기계적으로 판정 가능해진다. 이는 라이프니츠의 “계산해 봅시다(Calculemus!)” 이상의 실현이며, 힐베르트의 형식주의 프로그램의 최종 목표에 해당한다.

반대로, 판정 문제가 부정적으로 해결된다면, 수학적 추론에는 기계적 절차로 포착할 수 없는 본질적 측면이 존재한다는 것을 의미한다.

3. 튜링 이전의 관련 결과

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

괴델(Kurt Gödel)은 1931년 제1 불완전성 정리에서 페아노 산술을 포함하는 충분히 강력한 무모순 형식 체계에는 체계 내에서 증명도 반증도 불가능한 참인 명제가 존재함을 증명하였다. 이 결과는 힐베르트 프로그램의 완전성(Completeness) 목표가 달성 불가능함을 확정하였으나, 판정 문제 자체에 대한 직접적 해답은 아니었다.

괴델의 결과는 판정 문제의 부정적 해결을 강하게 시사하였지만, “효과적 절차“의 정밀한 수학적 정의가 부재하였기 때문에 판정 문제를 직접 해결하지는 못하였다.

3.2 “효과적 절차“의 정의 필요성

판정 문제에 대한 부정적 해답을 증명하려면, “효과적 절차가 존재하지 않는다“는 명제를 증명해야 한다. 이를 위해서는 “효과적 절차“라는 직관적 개념의 엄밀한 수학적 정의가 선행되어야 한다. 존재하지 않는 것을 증명하려면, 먼저 “무엇이 존재할 수 있는가“의 범위를 정밀하게 규정해야 하기 때문이다.

4. 튜링의 접근법: 인간 계산자의 분석

튜링의 독창적 기여는 “효과적 절차“의 개념을 인간 계산자(Human Computer)의 행동 분석으로부터 도출한 것이다. 튜링은 인간이 기계적 계산을 수행하는 과정을 관찰하고, 이 과정의 본질적 요소를 추상화하여 튜링 기계의 정의에 도달하였다.

튜링의 분석에 따르면, 인간 계산자의 기계적 계산 과정은 다음의 요소로 환원된다:

유한한 내적 상태: 계산자의 “정신 상태“는 유한한 수의 구별 가능한 상태 중 하나이다.
기호의 관찰: 계산자는 한 번에 유한한 수의 기호만을 관찰한다.
기호의 변경: 계산자는 관찰한 기호를 변경하거나 새로운 기호를 작성할 수 있다.
주의의 이동: 계산자는 관찰 대상 기호의 위치를 인접한 위치로 이동시킬 수 있다.
결정론적 행동: 각 단계에서의 행동은 현재 관찰하는 기호와 현재의 내적 상태에 의해 완전히 결정된다.

이 분석으로부터 튜링 기계의 정의가 자연스럽게 도출된다. 유한한 내적 상태는 유한 상태 제어 장치에, 기호의 관찰과 변경은 읽기/쓰기 헤드에, 주의의 이동은 헤드의 이동에, 기호가 기록된 매체는 무한 테이프에 대응한다.

5. 판정 문제의 해결

5.1 튜링의 증명(1936)

튜링은 1936년 논문에서 정지 문제(Halting Problem)의 결정 불가능성(Undecidability)을 증명하고, 이로부터 판정 문제의 결정 불가능성을 도출하였다.

정지 문제의 결정 불가능성 증명은 대각선 논법(Diagonalization)에 기반한다. 가정에 의해 정지 문제를 결정하는 튜링 기계 $H$ 가 존재한다고 하자. $H$ 를 이용하여 새로운 튜링 기계 $D$ 를 구성한다. $D$ 는 튜링 기계의 부호화 $\langle M \rangle$ 을 입력으로 받아, $H(\langle M \rangle, \langle M \rangle)$ 이 “정지함“을 출력하면 무한 루프에 진입하고, “정지하지 않음“을 출력하면 정지한다. $D$ 에 자기 자신의 부호화 $\langle D \rangle$ 를 입력하면 모순이 발생한다. 따라서 $H$ 는 존재할 수 없다.

5.2 처치의 독립적 증명(1936)

처치(Alonzo Church)는 튜링과 독립적으로, 동일한 시기에 람다 계산(Lambda Calculus)을 사용하여 판정 문제의 결정 불가능성을 증명하였다. 처치의 증명은 1936년 “An Unsolvable Problem of Elementary Number Theory“에서 발표되었으며, 시간적으로 튜링의 논문보다 수 개월 앞선다.

튜링은 자신의 논문에 부록을 추가하여 자신의 계산 가능성 개념(튜링 기계에 의한 계산 가능성)과 처치의 계산 가능성 개념(람다 정의 가능성, Lambda Definability)이 동치임을 증명하였다. 이 동치성은 두 독립적 형식화가 동일한 함수 클래스를 정의함을 보여주며, 처치-튜링 논제의 핵심적 근거이다.

6. 판정 문제 해결의 학문사적 의의

판정 문제의 부정적 해결은 다음의 학문사적 의의를 갖는다.

첫째, “효과적 절차” 또는 “알고리즘“의 엄밀한 수학적 정의가 확립되었다. 튜링 기계는 직관적 계산 가능성 개념의 수학적 포착이며, 이 정의가 계산 이론의 기초가 되었다.

둘째, 기계적 계산의 근본적 한계가 증명되었다. 알고리즘적으로 해결 불가능한 문제가 존재한다는 사실은 라이프니츠와 힐베르트의 이상에 대한 원리적 한계를 확정하였다.

셋째, 범용 튜링 기계의 개념이 현대 범용 컴퓨터의 이론적 모델을 제공하였다. 단일 기계가 프로그램에 따라 임의의 계산을 수행한다는 원리는 저장 프로그램 개념으로 구현되었다.

튜링의 학문적 배경에서 판정 문제의 해결로 이어지는 지적 경로는 순수 수학적 동기에서 출발하여 계산의 본질에 대한 가장 심원한 통찰에 도달한 과정이며, 이 통찰이 현대 컴퓨터 과학과 인공지능의 이론적 토대를 구축하였다.