1936년 5월 28일.
앨런 튜링의 논문이 런던 수학 학회(London Mathematical Society)에 공식적으로 제출되었다. 그 제목은 길고 학술적이었지만, 그 안에 담긴 파괴력은 학회에 모인 그 누구도 온전히 가늠하지 못했다.
「On Computable Numbers, with an Application to the Entscheidungsproblem」
(계산 가능한 수에 관하여, 그리고 결정 문제에의 한 응용)
논문 심사위원들은 첫 페이지를 넘기는 순간부터 당혹감과 경외감을 동시에 느꼈다. 알론조 처치가 이미 결정 문제를 해결했다는 사실을 알고 있었기에, 큰 기대를 하지 않았던 이들도 있었다. 하지만 튜링의 접근 방식은 그들의 예상을 완전히 뛰어넘었다.
논문은 이렇게 시작했다.
“이 논문에서 정의될 ‘계산 가능한 수’란, 그 소수점 이하 자릿수를 기계에 의해 계산해낼 수 있는 실수를 의미한다.”
시작부터 달랐다. 처치가 순수 논리의 세계에서 출발했다면, 튜링은 ‘기계’라는 구체적인 개념을 전면에 내세웠다.
심사위원들은 튜링이 묘사하는 상상 속 기계의 모습에 매료되었다.
무한히 긴 테이프, 그 위를 오가는 헤드, 유한한 개수의 상태.
그것은 복잡한 수학 공식이 아니라, 마치 공장의 조립 라인처럼 명확하고 직관적이었다. 그들은 튜링의 논리를 따라가며, 이 단순한 기계가 어떻게 덧셈과 곱셈 같은 계산을 수행하는지, 그리고 더 나아가 어떻게 자기 자신을 흉내 내는 ‘보편 기계’로 확장될 수 있는지를 숨죽이며 지켜보았다.
논문의 하이라이트는 결정 문제에 대한 증명 부분이었다.
튜링은 여기서 ‘정지 문제(Halting Problem)’라는 개념을 암시적으로 도입하며 논증을 전개했다.
그는 독자에게 다음과 같은 질문을 던지는 듯했다.
“모든 계산 규칙을 담고 있는 이 ‘보편 기계’에게, ‘자기 자신의 규칙표를 입력받았을 때, 과연 멈출 것인가, 아니면 영원히 계산을 계속할 것인가?’라고 묻는다면 어떻게 될까?”
이 질문은 논리적 함정이었다. 튜링은 이 질문에 답할 수 있는 기계는 원리적으로 존재할 수 없음을 귀류법을 통해 증명해냈다. 만약 그런 기계가 존재한다고 가정하면, 반드시 자기모순에 빠지기 때문이었다. (이 상세한 논증은 이후의 이야기에서 펼쳐진다.)
그리고 마침내, 그는 결론을 내렸다.
계산 기계가 자기 자신의 ‘정지’ 여부조차 판별할 수 없다면, 하물며 세상의 모든 수학적 명제의 참/거짓을 판별하는 것은 더더욱 불가능하다.
따라서 힐베르트의 결정 문제는 ‘풀 수 없다’.
이것으로 한 시대가 저물었다.
다비트 힐베르트가 세운, 수학의 모든 것을 알 수 있고 증명할 수 있으리라는 낙관적인 꿈은 공식적으로 끝났다. 쿠르트 괴델이 그 성벽에 첫 번째 균열을 냈고, 알론조 처치와 앨런 튜링이 마침내 그 성을 무너뜨린 것이다.
하지만 튜링의 논문은 파괴에서 끝나지 않았다.
그것은 폐허 위에 새로운 시대의 설계도를 제시했다.
논문의 진짜 가치는 결정 문제의 부정 증명에만 있는 것이 아니었다. 오히려 그 증명을 위해 튜링이 발명한 ‘튜링 기계’와 ‘보편 튜링 기계’라는 개념에 있었다.
그는 인류 역사상 최초로 ‘계산’이라는 모호한 지적 행위를, 수학적으로 엄밀하고 기계적으로 명확하게 정의해냈다.
그는 하드웨어와 소프트웨어가 분리된 현대적 ‘컴퓨터’의 이론적 모델을 제시했다.
심사위원들은 논문을 덮으며 깨달았다.
이것은 단순히 한 문제를 푼 논문이 아니다. 이것은 ‘계산 이론(Computation Theory)’이라는 새로운 학문의 탄생을 알리는 선언문이었다.
1936년 말, 튜링의 논문은 학회지에 정식으로 게재되었다. 스물네 살의 괴짜 천재가 던진 이 한 편의 논문으로, 수학의 시대는 저물고 ‘컴퓨터의 시대’가 막을 올릴 준비를 하고 있었다.
앨런 튜링의 이름은 이제 케임브리지를 넘어, 대서양 건너 프린스턴에까지 알려지기 시작했다.
그의 인생 1부가 ‘질문의 탄생’이었다면, 이제 막 2부 ‘기계의 증명’이 시작되려 하고 있었다. 무대는 프린스턴, 그리고 곧이어 닥쳐올 제2차 세계대전의 포화 속 블레츨리 파크로 옮겨갈 터였다. 그의 이론이 상상 속에서 걸어 나와 현실 세계를 바꾸게 될 시간이었다.
