나의 가장 이른 기억 중의 하나는 우리 집이 있던 동네 골목에서 한 친구 녀석과 뒹굴고(아마도 싸우고) 있는 모습이다. 당시에는 같은 골목에 사는 두 명의 또래 친구들과 늘 함께 놀았다. 그런데 어느 날부터인가 친구들의 모습은 보이지 않았고, 나는 외톨이가 되었다. 심심해진 나는 동네의 조금 껄렁한 형을 쫓아다니기 시작했다. 우리 동네에는 미군 부대가 있었는데, 그 형은 내게 미군들에게 접근해 초콜릿이나 돈을 얻어오라고 시켰다. 어느 날 미군 부대 근처에서 임무를 수행 중이었는데, 마침 근처를 지나시던 어머니에게 그 장면을 들키고 말았다. 큰 충격을 받으신 어머니는 바로 다음 날 나를 초등학교로 보냈다. 다른 아이들이 입학한 지 이미 한두 달이 지난 후였다. 사실 전에 함께 놀던 두 친구는 초등학교에 입학해 있었고, 한 살 적었던 나만 혼자 남겨진 것이었다. 그렇게 험난한 초등학교 생활이 시작되었다.

초등학교 교실에 가보니 다른 친구들은 익숙한 듯 여러 가지 활동을 했지만, 내게는 모든 게 생소했다. 깍두기 공책을 본 것도 그때가 처음이었다. 글자를 한 자씩 쓸 수 있는 작은 네모 칸으로 이루어진 공책인데, 그 네모 모양이 깍두기를 닮아 깍두기 공책이라 불렸다. 선생님이 시켰던지 나는 같은 글자(어쩌면 숫자)를 반복해서 네모 칸에 쓰고 있었는데, 공책 첫 페이지의 첫째 줄을 모두 채우고 나서는 (같은 페이지의 둘째 줄로 가지 않고) 다음 페이지 첫째 줄로 옮겨가 네모 칸을 채우기 시작했다. 그리고는 다시 다음 페이지 첫째 줄로 옮겨갔다. 그런 식으로 몇 페이지에 걸쳐 한 줄로 길게 늘어선 글자의 띠를 만들고 있는데, 그 모습을 본 짝이 놀라서 내게 말했다. “그거 그렇게 쓰는 거 아니야.”

영국의 수학자이자 암호 분석가인 앨런 매티슨 튜링(Alan Mathison Turing, 1912‒1954)이 (초등학교 1학년의 나처럼) 무한히 길게 한 줄로 늘어선 네모 칸을 따라 움직이며 기호를 읽고, 쓰고, 지우는 기계에 대한 논문을 제출한 때는 1936년이었다. 나중에 ‘튜링 기계(Turing Machine)’라 불리게 될 그 추상적인 자동 계산 기계는 독일의 수학자 다비트 힐베르트(David Hilbert, 1862‒1943)가 제안한 이른바 결정 문제(Entscheidungsproblem)를 해결하기 위한 이론적 장치였다. 그리고 튜링 기계는 현대 컴퓨터의 모태가 되었다.

앨런 튜링은 1912년 6월 23일 영국 런던에서, 영국령 인도의 행정 조직(Indian Civil Service) 소속의 줄리어스 매티슨 튜링(Julius Mathison Turing)과 에델 사라 튜링(Ethel Sara Turing, 결혼 전 성은 Stoney)의 둘째 아들로 태어났다. 어려서부터 수학과 과학에 관심이 많았던 앨런 튜링은 1931년, 케임브리지 대학의 킹스 칼리지에 입학해 수학을 전공으로 선택했다. 1933년, 버트런드 러셀(Bertrand Arthur William Russell, 1872‒1970)의 <수리철학의 기초>를 읽으며 수리논리에 관심을 가졌고, 1935년에는 영국의 수학자 맥스 뉴먼(Maxwell Herman Alexander Newman, 1897‒1984)이 가르치는 ‘수학의 기초’라는 수업을 들었다. 뉴먼은 1928년, 힐베르트가 독일을 대표했던 세계수학자대회(International Congress of Mathematicians, ICM)에 참석한 바 있었다. 힐베르트는 수학의 기초에 대한 질문을 제기했다. 첫째, 수학은 ‘완전’한가? 둘째, 수학은 ‘무모순적’인가? 셋째, 수학은 ‘결정 가능’한가? 힐베르트는 각각의 질문에 대한 답이 ‘그렇다’일 것이라 생각했다. 하지만 1930년, 오스트리아-헝가리 제국 출신의 수학자 쿠르트 괴델(Kurt Gödel, 1906‒1978)은 수학이 완전하지 않음을, 다시 말해 맞는다고도 틀리다고도 증명할 수 없는 주장이 존재한다는 것을 보였다. 또한 자체적인 공리 체계 내에서는 무모순성을 증명할 수 없음을 보였다. “뉴먼은 괴델의 정리를 증명하는 것으로 강의를 마쳤고, 이로써 앨런은 지식의 최전선에 다다른 셈이었다.”

(결정 문제라 불리는) “힐베르트의 ‘세 번째’ 질문은 여전히 해결되지 않은 채 남아 있었다. .. 수학적 명제의 증명 가능성 여부를 판별해줄 수 있는 명확한 방법(뉴먼의 표현대로라면 ‘기계적 과정’)은 존재하는가? .. “기계적 과정”이라는 뉴먼의 의미심장한 표현은 앨런의 머리를 맴돌았다.” 앨런 튜링은 자신의 추상적 자동계산 기계를 고안할 때, 종이 위에 수를 계산하는 인간을 떠올렸다.

사람들은 통상적으로 특정 기호를 종이에 쓰면서 계산을 한다. 이 종이가 어린이용 산수책처럼 네모 칸으로 구획되어 있다고 가정해보자. 초급 산술에는 2차원 형태의 종이가 가끔 사용되지만, 꼭 그럴 필요는 없다. 2차원 형태의 종이가 계산에 필수적이 아니라는 것쯤은 대체로 동의할 것이라 생각한다. 그러면 1차원 형태의 종이, 즉 네모 칸으로 구획된 테이프에 계산을 한다고 가정해보자.

그리고 그런 계산을 하는 인간을 유한한 개수의 상태만을 가질 수 있는 기계에 비유했다.

우리는 어떤 사람이 실수(a real number)를 계산하는 과정을, 유한한 개수의 상태 q₁, q₂,…, q_R만을 가질 수 있는 기계에 비유할 수 있다. 이 상태들은 “m-구성 상태(m-configurations)”라 불릴 것이다. 이 기계에는 그 속을 통과하는 “테이프”(종이의 유사물)가 공급되어 있으며, 테이프는 네모 칸(squares)으로 나뉘어 있고, 각 네모 칸은 하나의 기호(symbol)를 담을 수 있다. 어느 순간이든 오직 한 칸, 이를테면 기호 S(r)를 담고 있는 r번째 칸만이 “기계 안에” 있다.

기계가 어떤 순간에 취할 수 있는 행동은 기계의 m-구성 상태 q_n과 읽고 있는 기호 S(r)에 의해 결정된다. 기계는 네모 칸에 새로운 기호를 쓸 수도 있고, 읽은 기호를 지울 수도 있고, 현재 칸에 머물러 있거나 왼쪽 혹은 오른쪽으로 한 칸 움직일 수도 있다. 이러한 연산에 더하여 m-구성 상태가 변할 수도 있다. 튜링의 주장에 따르면, 이러한 연산들이 수를 계산하는 데 사용되는 모든 연산을 포함한다.

가장 간단한 예의 하나로 1111111.... 무한 수열을 만드는 튜링 기계를 생각해보자. 그 기계의 행동은 다음 표로 기술될 수 있다.

이 표는 다음과 같이 이해된다. 튜링 기계가 b라는 m-구성 상태에 있고, 읽고 있는 네모 칸이 비어 있다면(□), 그 칸에 1을 쓰고(P1), 오른쪽으로 한 칸 움직인다(R). 그리고 다음 m-구성 상태를 b로 바꾼다. (이 예에서는 b 상태를 유지한다.) m-구성 상태가 b인 튜링 기계가 아래 그림과 같이 테이프의 제일 왼쪽 칸(회색으로 칠해진 칸)에 놓여있다고 하자. (물론, 그 칸 왼쪽에도 무한히 긴 네모 칸들이 있다.)

튜링 기계가 놓인 칸의 기호를 읽어보면 빈칸이므로 기계는 그 칸에 1을 쓰고, 오른쪽으로 한 칸 움직인다. 그리고 m-구성 상태를 b로 바꾼다(여기서는 b로 유지된다). 옮긴 칸에서 기호를 읽어보면 다시 빈칸이므로 기계는 그 칸에 1을 쓰고, 오른쪽으로 한 칸 움직이고, m-구성 상태를 b로 유지한다. 이 동작이 계속 반복될 것이므로 아래 그림과 같은 결과를 얻는다. 물론, 이 그림의 오른쪽에도 무한히 긴 네모 칸들이 있고, 튜링 기계는 그 칸들을 계속 1로 채워나간다. 초등학교 1학년의 나는 바로 이런 튜링 기계와 다름없었다.

튜링이 실제로 튜링 기계의 첫 번째 예로 든 것은 0과 1을 번갈아 빈 네모 칸에 적는 기계였다. 즉, 010101.... 무한 수열을 만드는 기계다. 튜링은 한 칸씩 건너뛴 칸에만 수열을 쓰는 것을 선호했다. (숫자들 사이의 네모 칸들은 일종의 임시 메모장(scratchpad)으로 사용된다.) 그래서 010101... 수열은 테이프 위에 아래 그림과 같이 나타난다.

위와 같은 결과(010101.... 수열)를 얻을 수 있는 튜링 기계의 행동표(table of behavior)는 다음과 같이 주어진다.

이런 튜링 기계가 빈 테이프의 어떤 칸에서 m-구성 상태 b로 시작했다고 하자. 기계가 놓인 칸에서 기호를 읽어보면 빈칸(□)이므로 그 칸에 0을 쓰고(P0), 오른쪽으로 한 칸 움직인다(R). 그리고 m-구성 상태를 c로 바꾼다. 이제 m-구성 상태가 c인 기계가 빈칸(□)에 놓여있으므로 (아무것도 쓰지 않고) 오른쪽으로 한 칸 움직이고(R), m-구성 상태를 e로 바꾼다. 이제 m-구성 상태가 e인 기계가 빈칸(□)에 놓여있으므로 그 칸에 1을 쓰고(P1), 오른쪽으로 한 칸 움직인다(R). 그리고 m-구성 상태를 k로 바꾼다. 그러면 기계는 빈칸(□)을 만나 그냥 오른쪽으로 한 칸 움직이고(R), m-구성 상태를 b로 바꾼다. 이런 식으로 계속 반복되므로 결국 한 칸씩 건너뛴 칸들에 쓰여진 010101.... (무한) 수열을 얻게 된다.

튜링의 첫 번째 기계가 만드는 무한 수열 010101....을 (이진법) 무한소수 0.010101...로 간주하면 이것은 (십진법) 1/3에 대한 (이진법) 소수 표현이 된다. (모든 무리수는 아니지만) π, e 같은 무리수의 무한소수 수열을 만드는 튜링 기계도 있다. 튜링은 그 소수(小數) 표현이 (행동표를 따르는 튜링 기계 같은) 유한한 방법으로 계산될 수 있는 실수(real numbers)를 ‘계산 가능한 수(computable numbers)’라고 불렀다. 튜링은 인간 컴퓨터(computer)가 하는 일은 모두 기계가 할 수 있다고 주장했다. 그리고 어쩌면 기계가 (인간처럼) 생각할 수 있게 만들 수 있을지도 몰랐다.

(다음에 계속)