상상 속의 기계, 그 첫 번째 스케치

기숙사 방문이 쾅 닫혔다. 튜링은 숨을 몰아쉬며 책상으로 돌진했다. 그의 눈은 맹렬하게 타오르고 있었다. 강가의 산책에서 얻은 아이디어의 파편들이 머릿속에서 폭풍처럼 휘몰아치고 있었다. 그것들이 흩어지기 전에 붙잡아야 했다.

그는 펜을 움켜쥐고 노트의 깨끗한 페이지를 펼쳤다.

가장 먼저, 그는 자를 대고 길고 곧은 직사각형을 그렸다. 그리고 그 안을 작은 정사각형들로 꼼꼼하게 나누었다. 무한히 긴 종이테이프에 대한 상징이었다. 그는 각 칸에 ‘0’과 ‘1’, 그리고 비어있음을 나타내는 기호 ‘B’(Blank)를 몇 개 적어 넣었다.

[ B | 1 | 0 | 1 | 1 | B | B | ... ]

이것이 기계가 작업할 공간, 즉 ‘메모리’였다.

다음으로 그는 테이프의 한 칸 위를 가리키는 단순한 화살표(▼)를 그렸다.
이것이 ‘헤드(Head)’였다. 기계의 눈과 손. 헤드는 오직 자신이 가리키는 한 칸의 기호만을 ‘읽고’, 그 칸에 새로운 기호를 ‘쓸’ 수 있었다. 그리고 명령에 따라 왼쪽(L)이나 오른쪽(R)으로 한 칸씩 ‘이동’할 수 있었다.

[ B | 1 | 0 | 1 | 1 | B | B | ... ]
▲

여기까지는 단순했다. 진짜 핵심은 보이지 않는 곳에 있었다. 기계의 ‘마음 상태(State)’.
튜링은 노트의 한쪽 구석에 원을 그리고 그 안에 ‘S1’이라고 적었다. 이것이 기계의 현재 상태를 나타내는 기호였다. 기계는 한 번에 단 하나의 상태만을 가질 수 있었다. ‘덧셈 모드’, ‘탐색 모드’, ‘정지 모드’처럼.

이제 이 세 가지 요소를 연결할 ‘규칙’이 필요했다.
튜링은 노트 중앙에 표를 그리기 시작했다. 그의 펜은 망설임 없이 움직였다.

이것이 기계의 뇌이자 영혼, ‘행동표(Table of Behaviour)’였다. 이 표만 있으면 기계는 스스로 작동할 수 있었다. 그는 표의 첫 번째 줄을 채워 넣었다.

이 한 줄의 의미는 명확했다.
“만약 기계의 현재 상태가 ‘S1’이고, 헤드가 ‘1’이라는 기호를 읽는다면, 그 자리에 ‘0’을 쓰고, 헤드를 오른쪽으로 한 칸 이동시킨 뒤, 기계의 상태를 ‘S2’로 변경하라.”

그는 잠시 펜을 멈추고 자신이 그린 그림과 표를 내려다보았다.
완벽했다.
이보다 더 단순할 수는 없었다.
읽기, 쓰기, 이동, 상태 변경. 이 네 가지 단순한 행동의 조합만으로 모든 계산을 흉내 낼 수 있을 것 같았다. 모호했던 ‘확실한 방법(effective method)’이라는 개념이, 마침내 눈에 보이는 기계의 형태로 정의되는 순간이었다.

그는 이 상상 속의 기계에 이름을 붙였다. ‘자동 기계(Automatic Machine)’, 줄여서 ‘a-machine’.

이것은 단순한 낙서가 아니었다. 힐베르트의 결정 문제를 공격하기 위한 강력한 공성 무기였다. 지금까지는 ‘확실한 방법’이라는 개념 자체가 모호해서 공격할 대상조차 불분명했다. 하지만 이제 튜링은 명확한 적을 만들어냈다.

“모든 계산은 이 a-machine으로 표현될 수 있다.”

이것을 ‘가정’한다면, 이제 문제는 훨씬 간단해진다.
‘모든 문제를 풀 수 있는 a-machine이 존재하는가?’라는 질문으로 바뀌는 것이다. 그리고 만약 그런 만능 기계가 존재하지 않음을 증명할 수만 있다면, 결정 문제는 마침내 무너져 내릴 터였다.

튜링은 자신의 노트를 내려다보며 희미하게 미소 지었다. 그의 얼굴에 처음으로 자신감이 어렸다.
고독한 산책에서 시작된 아이디어는 이제 종이 위에 구체적인 생명을 얻었다.

이제 이 갓 태어난 기계가 정말로 ‘계산’을 할 수 있는지 시험해 볼 차례였다. 가장 간단한 것부터. 예를 들면, 1 더하기 1 같은.