깎아내기와 구축의 주기 법칙 · AI 연재 · 03

튜링은 한 가지 일이 불가능함을 증명하려 그 기계를 생각해 냈다

Han Qin · 읽는 데 약 24분 · 공개일

1. 주요 문제

규칙에 따라 문제를 푸는 일에는 한 가지 특징이 있다. 계산하는 사람이 그 뜻을 몰라도 된다.

덧셈 문제를 받고 세로셈을 따라 적으면, 수들이 무엇을 나타내는지 몰라도 맞힐 수 있다. 규칙은 종이 위에 있고, 사람은 실행만 한다.

19세기 말 수학자들은 더 큰 일을 생각하기 시작했다. 수학 문제도 모조리 이렇게 할 수 있을까. 아무 일차 논리식이나 하나 주었을 때 정해진 규칙을 유한 번 따라가기만 하면 그 식이 어떤 해석에서든 성립하는지 판단할 수 있을까.

똑똑한 사람에게 생각해 보라고 하는 것이 아니었다. 아무것도 모르는 사람도 시키는 대로 하면 해낼 수 있어야 했다.

당시에 이런 규칙 묶음을 절차라 불렀다. 그런 절차가 있는가. 1928년의 한 교과서가 수리논리학의 주요 문제로 지목한 물음이다.

그런 절차는 없다. 1936년에 증명되었다. 단정적으로 말하려면 증명하는 사람은 먼저 절차라는 것의 범위를 남김없이 정해야 했다. 그렇게 하려고 기계를 하나 만들었다.

훗날 컴퓨터의 모형이 된 바로 그 기계다.

1928년 베를린의 한 출판사에서 《이론 논리학 개요》라는 교과서를 인쇄했다. 다비트 힐베르트와 빌헬름 아커만이 썼다. 힐베르트는 괴팅겐의 수학 교수이자 당시 수학계에서 무게가 가장 큰 사람 가운데 하나였다. 아커만은 그의 제자였다.

책에는 이런 문제가 쓰여 있다. 논리식 하나가 주어지면, 일련의 조작을 유한 번 해서 어떻게 해석해도 성립하는지, 또는 적어도 한 가지 해석에서는 성립할 수 있는지를 판정하는 절차를 마련하라.

같은 쪽에는 이 문제를 평한 문장도 있다. 판정 문제를 수리논리학의 주요 문제라고 불러야 한다.

추천이 아니라 지목이었다. ‘해야 한다’고 썼다.

흥미롭다거나 연구할 만하다고 하지 않았다. 주요하다고 했다. 어떤 학문이 자기 핵심을 한 자리에 놓으면, 그 자리가 그 뒤에 하는 일을 재는 자가 된다. 누군가 해낸다면 그는 그 학문이 하려는 일을 해낸 셈이 된다. 불가능하다고 드러나면 학문도 그에 맞춰 제 모습을 한 번 바꿔야 한다. 1928년에 그 말을 쓴 책은 뒤의 경우를 위한 자리를 남기지 않았다. 교과서는 학생에게 배우라고 쓰는 책이지 의심하라고 쓰는 책이 아니다. 교과서에 넣는 것은 제대로 된 문제라고 공표하는 것이다. 제대로 된 문제에는 답이 있으리라는 것이 기본값이다.

앞서 비슷한 요구가 있었다. 1900년 8월 파리에서 힐베르트가 늘어놓은 문제 목록의 열 번째는, 특정 부류의 방정식이 주어졌을 때 유한 번 조작하여 정수해가 있는지 판정하는 절차를 요구했다. 1928년 요구보다 좁아서 특정한 산술 방정식 부류를 판정했다. 하지만 절차, 유한 번 조작, 판정이라는 말은 같았다. 28년 동안 범위가 넓어졌지만 요구의 모양은 바뀌지 않았다. 같은 연설의 총론에는 또 이런 말이 있다. 분명하게 제시된 수학 문제는 확정적인 해결을 얻거나 풀 수 없다는 증명을 얻어야 한다. 그때 뒷말은 물러설 길이었다. 36년 뒤 그것이 정문이 됐다.

1917년 취리히에서 그는 판정 가능성, 그리고 유한 번 조작으로 판정할 가능성을 연구 대상으로 꼽았다. 1922년 하인리히 베만은 논문 제목에 곧바로 판정 문제라는 말을 썼다. 참인지 거짓인지 가리는 일은 정해진 지시에 따른 기계적 계산으로 환원되어야 한다고 했다. 무엇이 필요한지 이미 드러난 문장이다. 지시 한 벌을 주고 생각하지 않고 따라가게 한다. 1922년에서 1923년으로 넘어가는 겨울 학기에 힐베르트와 파울 베르나이스는 괴팅겐에서 수학의 논리적 기초를 강의했다.

1900년에서 1928년으로 갈수록 요구는 분명해졌다. 그런데 그 안에서 한 가지는 좀처럼 분명해지지 않았다.

절차란 무엇인가.

‘유한 번 조작’에 나오는 조작은 어떤 동작을 뜻하는가. ‘정해진 지시를 따르는 기계적 계산’에서 기계적이라는 말은 어디까지 가리키는가. 아무도 정의하지 않았다. 1928년에는 정의할 필요가 없어 보였다. 수학자는 방법 하나를 보자마자 알고리즘인지 알아봤다. 알아볼 수 있으니 정의하지 않아도 됐다.

어떤 일이 불가능하다고 증명하려면 이 단계를 피할 수 없다. 먼저 가능한 모든 것을 하나도 빠짐없이 둘러야 한다. 그렇게 못 하면 존재하지 않는다고 할 수 없고, 아직 찾지 못했다고 할 수 있을 뿐이다. 찾지 못한 것은 증명이 아니다. 가능한 모양을 다 그려 내고서야 그 안에 없다고 할 수 있다. 튜링의 원고는 이런 모양이었다. 가능한 한 큰 우리를 만들고, 그 바깥에 무언가가 있다고 증명한다. 우리가 클수록 바깥에 있다는 사실은 더욱 확실하다. 제9절은 왜 이 우리가 빠짐없이 감쌀 수 있는지 설명한다. 누군가 빠졌다고 할 만한 곳을 하나씩 막으면서, 막을 때마다 문제를 푸는 사람에게서 무언가 하나를 가져온다.

꼬박 28년 동안 이쪽에서는 절차를 내놓으라고 했고, 저쪽에서는 절차가 어떻게 생긴 것인지 아무도 정하지 않았다. 요구는 이미 섰는데 요구하는 것이 모양을 갖추지 않았다. 구축된 틀이 바깥으로 손을 뻗어 자기 이름으로도 부르지 못하는 것을 잡으려 했다. 뒤의 일이 가능했던 까닭은 누군가 먼저 되돌아가 그 이름 없는 것을 만들었기 때문이다.

2. 두 회의장

1930년 9월, 쾨니히스베르크. 일주일 사이에 두 일이 일어났다. 훗날에는 곧잘 같은 일인 듯 이야기했다.

그중 하나는 뒤에 학문 전체를 바꿨다고 여겨졌으나, 현장에서는 아무도 곧바로 입을 열지 않았다. 한 해도 더 지나 논문이 나와서야 무슨 일이었는지 차츰 보였다. 일은 일어나는 순간 흔히 모양이 없다. 모양은 나중에 종이 위에 인쇄된다.

첫 번째는 9월 5일에서 7일까지 열린 제2회 정밀과학 인식론 회의였다. 경험철학 단체가 주최했다. 수학의 기초를 어떻게 놓을지 몇 학파의 견해가 한 치도 양보하지 않던 때였다. 5일에는 각 학파가 한 시간씩 말했고, 존 폰 노이만은 힐베르트 쪽의 입장을 발표했다. 6일에는 다른 강연들이 열렸다. 빈에서 온 스물네 살 쿠르트 괴델은 막 끝낸 작업을 20분 동안 소개했다.

일요일인 7일에는 한스 한의 사회로 수학의 기초에 관한 토론이 열렸다. 폰 노이만과 괴델 모두 발언했다. 토론이 끝날 무렵 괴델은 아직 정식으로 발표되지 않은 결과를 알렸다.

두 번째는 9월 8일 힐베르트가 한 《자연 인식과 논리》라는 연설이었다. 앞의 회의가 아니라 같은 도시에서 이어서 열린 독일 자연과학자 및 의사 학술대회에서 했다. 약 4분짜리 방송판의 녹음이 남아 있고, 끝에 그 문장이 있다. “우리는 알아야 한다. 우리는 알게 될 것이다.”

수학이라는 학문을 향한 말이었다. 원리상 알 수 없는 것은 인정하지 않겠다는 뜻이었다. 어떤 것은 사람이 결코 알 수 없고 거기까지라는, 당시 또 널리 퍼져 있던 말에 맞섰다. 그가 반대한 것은 그 ‘거기까지’였다. 6년 뒤 자기 학문에서 나온 결과가 이 길은 통하지 않는다고 증명했다. 하지만 그 증명의 모양은 그가 반대했던 ‘거기까지’와 다르다. 사람이 알아낼 수 없다고 한 것이 아니라 그러한 것이 존재하지 않는다고 했다. 두 말은 흔히 섞인다. 이 연재에서는 서로 아주 먼 자리에 있다. 앞말은 사람의 한계에 관한 말, 뒷말은 세계의 모양에 관한 말이다.

두 일은 하루 사이로 붙어 있다. 나중 이야기에서는 흔히 한 장면에 놓는다. 선언의 목소리가 채 가라앉기도 전에 옆방에서 그것을 무효로 만드는 결과가 나왔다고 한다.

그 주의 기록에는 두 사람이 만났다는 데가 없다. 9월 7일 토론의 참석과 발언 명단에 힐베르트는 없다. 다음 날 청중석에 괴델이 있었는지도 한 줄 언급되지 않는다. 두 방에서 따로 회의했고 상대를 들었다는 기록은 한 줄도 없다.

후대의 한 장면은 복잡한 일을 한 문장으로 만들었다. 그 주에 남은 종이는 달랐다. 수십 명이 두 회의로 나뉘어 저마다 말했고, 그중 한 사람이 일요일 오후 파할 때가 되어 무언가를 말했으며, 아무도 대꾸하지 않았다.

괴델의 1931년 논문은 수학 월간지에 실렸다. 관련은 있지만 다른 일을 다뤘다. 그가 연구한 부류의 형식 체계가 산술을 표현할 수 있고 해당하는 무모순성 조건을 만족하면, 어떤 문장은 증명할 수도 그 반대를 증명할 수도 없다. 체계란 규칙을 그렇게 고정해 적은 한 벌을 가리킨다.

그 논문이 교과서의 문제를 해결하지는 않았다. 판정 문제는 어떤 일차 논리식에든 통하는 보편적인 절차를 요구했다. 1931년 논문은 한 부류의 체계 안에 속한 문장에 관한 것이었다. 1936년이 될 때까지 판정 문제는 열려 있었다.

3. 1936년의 원고 세 편

1936년, 세 사람이 서로 다른 길에서 쓴 원고 세 편이 차례로 손에 잡혔다. 세 사람은 모두 같은 일에 닿았다. 규칙대로 계산한다는 것을 어떻게 정확하게 말할까. 하나는 함수항과 치환의 연산을, 하나는 띠와 행동표를, 하나는 칸의 열과 지시대로 일하는 사람을 썼다. 비슷한 생각은 제각기 시작할 수 있다. 같은 것인지는 따로 공을 들여 증명해야 한다. 증명하고 나면 몇 갈래 길이 원래부터 한 길인 것처럼 보인다.

3월에 새로 나온 기호 논리학 학술지 창간호에는 프린스턴의 알론조 처치가 쓴 두 쪽짜리 논평이 실렸다. 제목에 판정 문제가 바로 들어 있다. 4월에는 미국의 한 수학 학술지에 19쪽짜리 긴 글 《초등 정수론의 한 해결 불가능한 문제》가 나왔다.

5월 28일 런던수학회에 원고 한 편이 도착했다. 케임브리지 킹스 칼리지의 스물세 살 연구원 앨런 튜링이 썼다. 제목은 《계산 가능한 수와 판정 문제에의 한 가지 응용》. 논문은 11월 12일 발표되었고, 인쇄본은 36쪽이다.

10월 7일 기호 논리학 학술지는 세 번째 원고를 받았다. 미국 수학자 에밀 포스트가 쓴 《유한 조합적 과정: 제1정식화》였다. 세 쪽으로, 세 자료 중 가장 짧다. 창간한 지 얼마 되지 않은 학술지에 실렸는데, 편집자 가운데 한 사람이 바로 3월과 4월 논문의 저자였다. 한 사람의 이름이 그해에 세 번 나왔다. 저자로, 뒤에서 따라잡으려는 이들의 상대로, 원고를 받는 편집자로. 이듬해에는 서평을 쓰는 사람과 지도교수로 또 나올 것이다. 그 기계의 이름을 붙인 사람도 그였다.

튜링은 논문 첫머리에서 처치의 최근 연구가 이미 불가능하다는 결과를 내놓았다고 인정했다. 부록에서는 자기 계산 가능성이 처치의 정의 가능성과 등가임을 증명했다.

부록을 보면 논문이 제출된 뒤에 바뀌었음을 알 수 있다. 한 사람이 이미 같은 결론에 먼저 이르렀고, 그래서 자신의 길과 상대의 길이 같은 곳에 닿는다고 증명해야 했다. 원래 하려던 증명이 아니다. 일어난 순서에 밀려 들어온 증명이다.

이 일에 관해 이듬해 튜링이 한 말이 또 있다. 1937년 두 정식화를 비교한 글 첫머리에서 자기 것이 아마 더 설득력 있을 것이라고 했다. 수학적으로는 등가지만 설득력까지 등가인 것은 아니다. 차이는 결론이 아닌 이유의 모양에 있다.

포스트의 세 쪽이 인쇄될 때 그 밑에 편집자 주가 붙었다. 곧 나올 튜링의 논문과 비교해 보라고 권했다. 포스트 논문의 날짜가 뒤지만 글은 완전히 독립적으로 썼다고 특별히 밝혔다.

여기까지가 1936년의 사실이다. 처치와 튜링은 저마다 판정 문제를 해결하는 절차가 없음을 증명했다. 포스트는 독립적으로 다른 계산 모형을 내놓았고, 괴델과 처치가 말한 재귀와 등가일 것으로 보았다. 그의 세 쪽은 같은 결론의 세 번째 증명이 아니다.

두 형식적 정의가 등가라는 점은 훗날 중요한 증거로 여겨졌다. 하지만 1936년 튜링에게는 두 길이 어디서 만나는지 보이기 전에 자기 방법과 처치의 방법이 같은 부류를 계산한다고 애써 증명할 일이 남아 있었다.

1937년 튜링은 세 쪽의 정정문을 냈다. 원문의 오류를 지적한 사람은 베르나이스라고 밝혔다. 거듭 기초를 놓은 업적이라 불린 글도 나온 지 1년 안에 누군가가 잘못을 찾아냈다. 고치고 나서도 기계와 결론은 남았다.

4. 지금 문제를 풀고 있는 사람

튜링의 논문 제9절 첫머리에는 아직 하지 못한 일이 쓰여 있다. 그가 형식화한 ‘계산 가능’이라는 말이 사람들이 보통 계산 가능하다고 부르는 모든 것을 담을 수 있다는 것은 그때까지 증명하지 못했다.

세 가지 이유를 댄다. 첫째는 바로 직관에 호소하는 것, 둘째는 서로 다른 정의가 등가임을 증명하는 것, 셋째는 많은 예를 드는 것이다.

이 부류의 논거가 살피는 대상은 바로 지금 종이와 기호로 문제를 푸는 사람이다.

1936년의 영어에서 계산자라는 말은 사람이었다. 직업이자 이력서에 쓸 수 있는 직함이었다. 사람들이 책상에 앉아 주어진 규칙대로 한 단계씩 계산해 표를 만들었다. 천문표, 항해표, 보험에 쓰는 표도 이렇게 만들었다. 그런 사람은 어디에나 있었다. 대개 반복 작업을 하도록 고용되어 방 하나에 줄지어 앉아 저마다 한 구간을 맡았다. 그 말이 기계에 넘어간 것은 몇십 년 뒤였다. 넘어간 뒤 그 사람들에게는 다른 이름이 붙거나 아무 이름도 붙지 않았다. 직업 이름이 기계로 건너간다는 것은 보통 그 일이 더는 일로 셈해지지 않는다는 뜻이다. 튜링이 이 절에서 계산하는 사람을 가리킨 대명사는 ‘그’였다.

그는 한 문장을 적었다. 어느 순간 그 사람이 하는 행동은 그 순간 보고 있는 기호로 결정된다. 바로 뒤에 그때의 마음 상태도 결정 요인으로 더했다.

그러니 시작부터 모형에는 두 가지가 있다. 보이는 기호와 보이지 않는 상태. 이 절은 뒤의 것도 보이게 하는 방향으로 나아간다. 못 하면 다른 것으로 바꾼다. 제9절의 세 번째 논증이 쓰는 방식이자 이 논문 전체의 방식이다.

그런 다음 그는 한 가지씩 범위를 좁힌다. 매번 수학적으로 무엇이 편한가가 아니라 사람이 무엇을 해낼 수 있는가에서 출발한다.

종이는 보통 이차원이다. 그는 그것을 칸칸이 나눈 띠로 바꾸었다. 사람들이 실제로 종이띠를 쓰기 때문은 아니다. 이차원은 계산의 본질이 아니므로 이차원 배치를 피할 수 있기 때문이다.

쓸 수 있는 기호의 종류는 유한해야 한다. 이유는 수학이 아니라 경험에 있었다. 글자가 아주 길게 이어진 것을 복합 기호 하나로 보면, 길어졌을 때 한눈에 알아보지 못한다. 예로 9가 빽빽하게 늘어선 아주 긴 두 줄을 들었다. 한눈에 둘이 같은지 알 수 없다.

이유는 경험적이지 형식적이지 않다. 엄밀함을 무엇보다 중히 여기는 학문의 기본 개념을 정하면서, 사람이 눈으로 한꺼번에 다 볼 수는 없다는 것을 증거로 삼았다. 여기서 모형의 경계는 인간의 능력에 맞춰 쟀다. 물리나 논리가 아니라 사람이 한눈에 제대로 알아볼 수 있는가를 보고 그었다. 훗날에는 흔히 기계 자체의 성질로 여겨졌다.

한 순간에 볼 수 있는 칸 수에는 상한이 있다. 튜링은 글자 하나로 그 수를 표시했다. 더 보려면 하나씩 계속 봐야 한다.

고려해야 할 마음 상태의 수도 유한해야 한다. 무한하게 많다고 하면 서로 얼마든지 가까워지는 상태가 생겨 헷갈리기 때문이다. 복잡한 상태의 일부는 밖으로 옮겨 띠 위에 기호를 더 쓰는 것으로 바꿀 수 있다.

그 문장에 동작 하나가 있다. 밖으로 옮긴다. 마음에 담을 것이 너무 많으면 종이에 적는다. 종이에 적고 나면 더는 마음에 있지 않다. 마음에 덜 남을수록 덜 가정해도 된다. 덜 가정할수록 논증은 견고해진다. 그래서 이 절은 계속 밖으로 쏟아내는 쪽으로 간다. 안의 것을 종이에 쏟아, 안이 빌 때까지.

다음에 눈을 어디에 둘 수 있는지도 한정된다. 정해진 거리가 있어 새로 볼 칸이 방금 본 칸에서 너무 멀어서는 안 된다. 멀리에 번호가 붙은 칸은 한눈에 알아볼 수 있는 듯하다는 반례도 검토했다. 번호가 길어지면 결국 글자를 하나씩 대조해야 한다고 답했다.

이 가정들을 합쳐 튜링은 이 사람의 계산을 재현할 기계를 만들었다. 사람이 고려하는 마음 상태 하나마다 기계 내부의 한 구성이 대응한다. 기계는 그에 맞는 수만큼 칸을 훑고 일정한 거리 안에서 보는 자리를 바꾼다.

기계가 재현하는 것은 여기서 분석한 기호 계산 과정의 한 구간이다. 정해진 규칙대로 문제를 푸는 사람이 하는 일이다. 구체적이고 따분하며, 이전부터 누군가 돈을 받고 했다.

같은 해 가을 다른 사람은 같은 것을 다른 모양으로 세 쪽에 적었다. 포스트는 양쪽으로 끝없이 이어진 칸들을 기호 공간으로 구상했다. 각 칸은 비어 있거나 표시가 있다. 거기서 일하는 사람은 문제 해결자 또는 작업자라 불렀다. 사람은 한 칸에서 작업하며 고칠 수 없는 정해진 지시를 따른다. 기본 동작은 지금 칸에 표시가 있는지 보기, 지우기, 표시하기, 오른쪽 한 칸, 왼쪽 한 칸이다.

두 원고 사이에 대서양이 있다. 쓰는 말은 달라도 출발점은 같았다. 사람 하나, 종이 한 묶음, 바꿀 수 없는 규칙 한 벌.

두 사람이 저마다 계산이 무엇인지 생각했을 때 가장 먼저 떠올린 것은 일하는 사람이었다. 시계도, 베틀도, 회로도 아니었다. 계산에 관한 모형을 만들려 했고, 그때 세상에서 계산을 가장 닮은 것은 정해진 규칙대로 문제를 푸는 사람이었다.

5. 종이 위의 쪽지

제9절에는 세 번째 처리 방식이 있다. 튜링은 이 논증에서 마음 상태 대신 종이 위에 둘 것을 찾았다. 첫 논증에는 남이 볼 수도 확인할 수도 없는 것이 하나 있었는데, 논문 전체는 어떤 일을 더 묻지 않아도 될 만큼 확실하게 말하려 했다.

계산하던 사람이 멈추고 떠나 하던 일을 잊어버려도, 종이에 남긴 지시 쪽지를 읽고 돌아와 계속할 수 있다고 그는 생각했다. 그 쪽지와 띠에 이미 적힌 기호를 함께 놓으면 마음 상태에 좀 더 분명하게 대응하는 물리적 물건이 된다.

이렇게 처리했다. 마음 상태가 없다거나 중요하지 않다고 하지 않았다. 무엇인지 연구하지도 않았다. 그것 없이도 논증이 굴러가도록 다른 것을 찾았다. 남이 확인할 수 없는 것이 있던 자리에 종이 한 장을 놓았다. 종이는 다른 사람에게 건넬 수 있고, 베껴 쓸 수 있고, 맞춰 볼 수 있고, 이어받아 계속할 수 있다. 누군가 이어서 해도 되는 일이 되는 순간 처음의 사람은 더 필요하지 않다. 1936년 이 말은 논증의 한 단계였고, 그 뒤 백 년 동안 많은 사람이 처한 형편이었다. 그러나 이 절에서는 아직 확인할 수 없는 가정을 없애기 위한 편의였다.

심지어 그 사람이 앉을 때마다 한 단계만 하고 다음 단계의 지시를 적도록 했다. 그러면 각각의 단계까지 진행한 계산의 상태 전부를 쪽지와 띠의 기호에 남길 수 있다.

그 사람 대신 다른 사람을 앉혀도 된다. 쪽지를 읽고 한 단계를 하고 새 쪽지를 써 놓고 가면 된다. 할 일이 종이에 다 적혀 있으니 누가 그 한 단계를 하든 결과는 달라지지 않는다. 그 순간 일하는 사람은 바꿔 끼울 수 있게 된다. 첫 번째 논증에서 그는 아직 자기 마음 상태를 가지고 있었다. 세 번째 논증에서는 그와 그의 마음 상태를 함께 종이로 옮겼다. 그러고 나면 원래 자리에 누가 있는지는 상관없다.

이 수법은 그 뒤에도 쓰였다. 닿지 않는데 피해 갈 수도 없는 것에 마주치면 닿을 수 있는 대역을 하나 찾아 넣고 논증을 이어 간다. 대역이 쓸 만한지는 논증이 끝까지 가는지 보면 된다. 바뀌어 나간 것이 대체 무엇이었는지에는 더는 답하지 않아도 된다.

튜링이 한 일은 종이와 펜으로 하는 구체적 노동 하나의 모형을 만든 것이다. 뒤에 사람들이 한 말은 그 모형이 곧 마음의 모형이라는 것이었다. 두 말 사이에 온전한 길 하나가 놓여 있다. 1936년의 그 36쪽은 그 길에 한 걸음도 들여놓지 않았다.

뒤에서 거듭 만나게 될 장면을 여기서 본다. 대역이 논증에 들어가면 그 자리에 남는다. 논증이 잘 통하고 나면 대역이 본래의 것이 된다. 바뀌어 나간 쪽은 거짓으로 드러난 것도, 옳다고 인정된 것도 아니다. 다만 차츰 입에 오르지 않게 된다.

6. 모든 기계 노릇을 할 수 있는 기계

논문 제6절의 제목은 범용 계산기다.

튜링은 첫머리에 단일한 기계 한 대를 설계할 수 있다고 썼다. 다른 기계의 표준 기술을 이 기계에 넣으면 다른 기계가 내는 것과 같은 수열을 계산한다고 했다. 제7절에 이 기계의 완전한 행동표가 나온다.

이 기계는 다른 기계에 대한 기술을 데이터로 먹어 들인다. 기술과 그 기술이 가리키는 것이 같은 띠 위에 놓였다. 한 기계의 사양이 다른 기계가 처리할 기호가 된다. 1936년에는 증명하기 편하려고 한 일이었다. 훗날에는 산업 하나의 전제가 됐다.

이 기계가 차지하는 자리는 특별하다. 여러 기계에서 가장 힘센 기계가 아니다. 그중 어느 기계 노릇이든 할 수 있는 기계다. 이 부류에서 해낼 수 있는 일은 모두 해낸다. 여기서 구축된 틀이 처음으로 자기 부류 안에서 닫혔다. 안에는 닿지 않는 것이 더는 없다.

앞서 나온 틀들은 다 바깥으로 자랐다. 한 치 자라면 바깥이 한 치 줄지만, 바깥은 늘 있었다. 이 기계는 다르다. 한꺼번에 자기 부류를 채워 더는 바깥으로 자랄 필요가 없다. 다른 일을 시키려면 개조할 필요 없이 넣어 주는 기호만 바꾸면 된다. 자카르 직기도 일찍이 카드를 바꿀 수 있었고, 나무 피아노도 전제를 바꿀 수 있었다. 하지만 그것들이 바꿀 수 있는 것은 저마다의 규칙 안에 있었다. 이 기계는 기계와 기계가 할 일을 갈랐다. 그러고 나자 기계라는 말도 뜻이 달라졌다. 어떤 일을 위해 만든 물건에서, 일을 맡기기를 기다리는 물건이 됐다. 맡기는 사람은 여전히 바깥에 있다. 무엇을 맡길지, 누가 정할지, 이 두 가지는 이 기계가 넘겨받지 않았다. 이 글은 두 가지를 다루지도 않았다. 그 뒤 누군가 새로운 일 한 조각을 기계 안으로 옮길 때마다 두 일은 제자리에 남았다.

바로 그 글의 제8절이 부정적 결론을 내놓는다. 기계에 대한 기술을 어떤 것이든 넣었을 때, 기술된 기계가 튜링이 정의한 어떤 부류에 속하는지 언제나 판정하는 일반 절차는 없다. 제11절에서는 이 판정 불가능성을 1928년 교과서의 논리 기호 체계로 옮긴다. 끝에 결론을 썼다. 여덟 해 전 수리논리학의 주요 문제로 지목된 문제에는 해법이 없다.

한 글에 두 일이 있다. 구축된 틀이 자기 부류 안에서 닫혔다. 동시에 그 밖이 있다고 증명되었다.

두 일은 같은 틀에서 나왔다. 어떤 기계든 기호의 열로 써서 그 한 대에 넣을 수 있기에, 그 열로 방금의 구성을 해낼 수 있다. 같은 부류의 무엇이나 흉내 낼 수 있기에, 그 기계가 답할 수 없는 문제도 물을 수 있게 된다. 닫힘과 바깥이 있음은 두 결과가 아니다. 한 결과의 두 면이다.

더구나 이 바깥은 잠정적인 것이 아니다. 기술이 진전된다고 사라지거나, 기계를 더 크고 빠르게 만든다고 들어설 수 있는 바깥이 아니다. 증명된 바깥이다.

앞 두 편의 경계는 사람이 그었다. 기계를 보고 여기까지라고 했다. 이번에는 사람의 판단이 아니라 기계 자신의 규칙에서 한계가 나왔다. 사람이 생각을 고쳐먹는다고 옮길 수 없다. 그 뒤로 누군가 기계가 무슨 일을 할 수 없다고 할 때마다 물을 수 있다. 이런 종류의 불가능인가, 저런 종류인가. 이 연재에서 처음으로 남는 몫은 누군가 손가락으로 여기 남았다고 짚은 것이 아니라 구축된 틀 자체의 규칙에서 이끌어 낸 것이다.

훗날 널리 알려진 정지 문제로 비유하면 이런 논법이다. 그런 판정 절차가 있다고 가정한다. 그것을 이용해 자기 자신에게 딴죽을 거는 기계를 만든다. 그 기계가 하리라고 판정된 일은 기어이 하지 않도록 한다. 그러면 그 절차는 이 기계에 앞뒤가 맞는 답을 주지 못한다. 어떤 기계에서도 답을 줘야 하는 절차인데 그러지 못한다. 가정이 성립하지 않는다. 이런 논법을 대각선 논증이라 한다. 튜링 원문의 제8절에서 물은 것은 기계가 출력을 계속할 것인지, 그리고 기계가 지정된 기호를 인쇄할지 판정할 수 있는지였다.

논문에서 이 기계는 여기까지 오기 위해 쓰였다.

어떤 일을 정확히 말하려면 먼저 할 수 있다는 것이 무엇인지 밝혀야 한다. 이 글에서 할 수 있다는 말은 기계 한 대의 모양을 얻었다. 훗날 계산 모형이 된 것이 여기서는 부정적 결론의 한 고리였다.

그 기계는 증거로 쓰였다. 어떤 절차도 특정한 일을 해내지 못한다고 증명하려면 먼저 절차가 어떤 모양일 수 있는지 말해야 한다. 그래야 가능한 모든 절차를 한 그물에 넣고 거기서 못 하는 일을 가리킬 수 있다. 기계가 그 그물이다. 그물을 짠 사람이 잡으려던 것은 기계가 아니라 절차였다. 그물을 다 짜고 난 뒤 남은 것은 그물 자체였다.

7. 이름은 나중에 붙었다

그 36쪽에 지능이라는 말은 한 번도 나오지 않았다.

마음이라는 말은 나온다. 거의 모두 제9절에 거듭 나오는 그 사람의 마음 상태를 뜻한다. 기계에 마음이 있다는 주장이 아니었다. 계산하는 사람의 상태 변수 하나였고, 그것도 세 번째 논증의 쪽지에 곧 자리를 내준다. 나중에 이 글을 인용할 때 흔히 거꾸로 읽었다. 사람에 관한 변수가 기계에 관한 약속으로 읽혔다.

생각한다는 말도 ‘내 생각에는’, ‘누군가는 이렇게 생각할 수 있다’ 같은 일상적인 말에 나왔다. 기계가 생각할 수 있느냐는 질문은 논문에 없었다.

그 뒤 80년 동안 이 논문은 흔히 그 질문의 출발점으로 여겨졌다. 실제로 답한 것은 다른 질문이다. 그런 절차는 있는가. 1900년부터 1936년까지 36년을 물었고, 답은 없다는 것이었다. 그 답을 내놓으려면 먼저 계산하는 일이 무엇인지 전부 정해야 했다. 정해 놓고 보니 부정의 답은 몇 쪽에 그쳤고, 정의는 남았다.

또 나오지 않는 낱말이 있다. 튜링 기계. 그는 계산 기계, 자동 기계, 선택 기계, 범용 계산기라고 썼다.

그 이름은 1937년 3월에 처치가 이 논문에 대해 쓴 서평에서 나왔다. 두 달 앞서 같은 결론에 닿은 동료가 논문이 인쇄된 이듬해 그것을 평하며 이름을 붙였다. 처치는 같은 서평에서 두 방법을 직접 대조했다. 튜링의 계산 가능성을 보면 그것이 통상적인 의미의 유효성과 일치한다는 점이 곧바로 드러난다고 했다. 먼저 결과를 낸 사람, 그 학술지의 창간 편집자 가운데 한 사람, 튜링의 다음 두 해 지도교수가 될 사람이 한 말이다.

다른 이름들은 더 늦게 나왔다. 처치 논제라는 이름은 논리학자 스티븐 클레이니가 1952년 메타수학 교과서에서 부르기 시작했다. 처치와 튜링을 합친 이름은 클레이니의 1967년 책에 나온다. 1936년의 세 당사자 누구도 이런 이름을 쓰지 않았다. 31년 뒤에야 두 이름을 나란히 넣은 이름이 생겼다. 그때 당사자 중 한 사람은 이미 세상에 없었다. 이름은 남이 붙였고, 붙일 때 부름을 받는 사람은 그 자리에 없었다. 이 연재에서 벌써 세 번째다.

포스트는 자기 글 세 쪽의 마지막에 이름에 관한 경고를 남겼다.

유효하게 계산할 수 있다는 뜻을 형식적인 어느 부류와 같다고 놓는 처치의 접근을 계속 검증할 작업 가설이라고 했다. 그런 동일시를 ‘정의’라는 말 밑에 감추는 데 명확히 반대했다. 그러면 “계속 검증할 필요가 있다는 점을 보지 못하게 된다”는 말로 문장이 끝난다.

이 말은 1936년에 나왔다. 일이 막 이루어졌을 때, 그것을 정의라 부르면 더는 검증하지 않아도 된다는 선언과 같다고 누군가 지적했다.

그가 지키려던 것은 기술상의 작은 구분이 아니었다. 정의는 약속이다. 약속을 두고 세계가 맞는지 틀리는지 따지지 않는다. 가설은 주장이다. 주장은 뒤집힐 가능성에 계속 열려 있다. 같은 명제를 어느 이름 아래에 놓느냐에 따라 누군가 그 뒤에도 들여다봐야 하는지가 달라진다. 이름 하나가 모두를 대신해 일을 끝내 버리게 하지 말자는 것이었다.

훗날에는 실제로 정의와 논제라는 두 이름이 번갈아 자리를 차지했다. 포스트가 그 단락을 쓸 때는 두 이름 모두 나오지 않았다.

8. 괴델은 어느 쪽을 골랐나

튜링은 1936년 9월 말 프린스턴에 도착해 2년 동안 대학원에서 공부했다. 지도교수는 처치였다. 1938년 그곳에서 박사 학위를 받았다. 1938년 4월 폰 노이만이 남아 자기 조수가 되라고 했다. 사양하고 케임브리지로 돌아갔다.

튜링이 프린스턴에 있던 2년 동안 괴델은 거기에 없었다. 두 사람 사이에 편지 한 통, 회의 메모 한 줄, 공동 논문 한 편도 남지 않았다. 나중 이야기에는 두 이름이 흔히 나란히 나온다. 놓기가 너무 쉽기 때문이다.

튜링 이전에 괴델은 처치의 방법에 만족하지 않았다. 처치는 1935년 11월 편지에서 괴델이 정의 가능성을 유효 계산 가능성의 정의로 삼는 제안을 전혀 받아들일 수 없다고 봤다고 썼다. 괴델은 당시 유효 계산 가능성을 먼저 공리화하려는 쪽에 더 기울었다.

1946년 프린스턴 개교 200주년을 맞은 수학 회의에서 괴델은 이 작업이 중요한 까닭을 말했다. 고른 기호 체계에 매이지 않는 절대적인 정의를 처음으로 주었다는 것이다. 그가 강조한 것은 개념의 절대성이었다. 절대적이라는 것은 형식 체계를 바꿔도 개념이 따라 바뀌지 않는다는 뜻이다. 그가 쓴 말은 ‘처음’이었다. 괴델이 보기에 1936년 이전에는 어느 시도도 여기까지 오지 못했다. 자신이 1934년 프린스턴에서 했던 강의도 그랬다. 앞선 정의들은 어느 기호 체계에 붙어 있어 바꾸면 처음부터 해야 했다.

1963년, 괴델은 자기 1931년 논문에 주석을 달았다. 특히 튜링의 업적 덕분에 이제 형식 체계라는 일반 개념에 정확하고 의심할 여지 없이 충분한 정의를 줄 수 있다고 했다. 진정한 뜻의 형식 체계라면 체계 안에서 하는 추론을 원리상 완전히 기계 장치로 대신할 수 있다는 특징이 있다고 덧붙였다.

1963년에 쓴 주석이 1931년 논문 뒤에 붙었다. 32년 뒤 그때 없었던 것을 논문에 보탰다. 형식 체계가 무엇인가 하는 것이다. 그것을 채운 것은 1936년 다른 일을 하려고 만든 모형이었다.

1964년, 괴델은 1934년의 강의록에 후기를 붙였다. 튜링의 작업이 기계적 절차라는 개념을 분석했다고 썼다. 같은 후기에서 다른 물음은 닫지 않았다. 유한하지만 기계적이지 않은 절차가 존재하는가.

이 틀에 인장을 찍은 사람이 같은 문서에서 자신은 그것을 사람의 모든 마음 과정에 대한 정의로 넓히지 않는다고 밝혔다. 받아들인 것은 구체적인 한 가지였다. 기계적 절차라는 개념이 분명하게 분석됐다. 그 바깥에 다른 것이 있는지는 물음으로 적어 놓고 답하지 않았다.

말년의 대화에서는 더 강하게 말했다. 튜링 전에 사람들은 기계적 절차의 분명한 개념을 꿰뚫어 보지 못했고, 튜링이 올바른 관점을 가져왔다고 했다. 튜링 기계에서 실행할 수 있는가로 범위를 잡는 것은 옳고 유일한 정의라고도 했다.

여기서 남는 몫은 이 틀에 인장을 찍은 사람이 자기 손으로 남겨 두었다.

그는 그 모형을 무게 있게 인정했고, ‘의심할 여지 없이 충분하다’고까지 했다. 같은 곳에서 더 큰 물음은 줄을 바꿔 적었다. 거기까지 밀고 나가지 않았다.

1947년 철학자 루트비히 비트겐슈타인은 한 권의 원고에 이렇게 썼다. 튜링의 그 기계들. 이 기계들은 바로 계산하고 있는 사람들이다.

이어지는 문장은 튜링이 한 말을 게임 형태로도 표현할 수 있다고 한다. 그 다음에는 자기 나름으로 바꾼 대각선 논증을 쓰고 규칙이 어떤 자리에서 뜻없는 지시가 되는 사정을 다룬다. 사람과 기계에 관해 말할 때 자주 인용되는 이 문장을 쓰며 그는 대각선 논증 문제를 풀고 있었다.

논문이 찍혀 나온 뒤 처음 3년 동안 이름을 댈 수 있는 독자들은 이렇다. 뉴먼은 투고 전에 이미 알고 함께 이야기했다. 처치는 서평을 썼다. 베르나이스는 틀린 곳을 찾아낼 만큼 읽었다. 1937년 2월 튜링은 비트겐슈타인에게 별쇄본도 보내게 했다.

명단은 여기까지다. 선생 한 사람, 경쟁자 한 사람, 틀린 곳을 짚은 한 사람, 그리고 보낸 별쇄본 한 부.

1948년 뉴먼은 왕립학회 회보에 《범용 계산 기계 설계의 일반 원리》를 싣고 튜링의 범용 기계를 논했다. 그때는 범용 전자 계산 기계를 만드는 일이 이미 공학 문제가 되어 있었다. 이 글을 쓴 사람은 바로 12년 전에 튜링에게 그 문제를 강의한 사람이었다. 당시에는 강의실에서 논리 문제를 다뤘고, 12년 뒤에는 어떻게 만들지 설명했다. 문제는 같고, 무엇에 썼는지가 달랐다. 같은 물건을 12년 전에는 어떤 일을 할 수 없다고 증명하는 데 썼고, 12년 뒤에는 기계를 설계하는 법을 설명하는 데 썼다. 어떤 것은 존재하지 않는다고 증명됐다. 그 부재를 증명하려고 만든 도구는 남아, 실제 물건으로 제작됐다. 이 연재에서 모양은 달라도 같은 일이 다시 생긴다.

1930년 9월 그 며칠의 완전한 청중 명단은 없다. 괴델이 그 일요일 오후 누구를 향해 그 말을 했는지, 누가 듣고 누가 듣지 못했는지 오늘날 아무도 다 열거하지 못한다. 그런데 나중에 그려진 장면을 떠받치는 것이 바로 그 존재하지 않는 명단이다.

스물세 살의 한 사람이 1936년 봄 원고 한 편을 마쳤다. 할 수 없는 일이 하나 있음을 증명하려고 썼다. 책상 앞에 앉아 문제를 풀던 사람에게서 기계 한 대를 벗겨 냈다. 그 기계는 훗날 실제로 만들어졌고, 여러 이름으로 불렸고, 그 글에서 한 번도 나오지 않은 질문을 하는 데 쓰였다.

그 물음을 튜링 자신이 한 것은 열네 해 뒤였다. 그때 그는 이미 실제 기계를 곁에 두고 있었다. 그리고 그 기계를 벗겨 내 온 자리의 사람, 책상에 앉아 규칙대로 문제를 풀던 사람은 더는 계산자라 불리지 않았다.

기계는 계속 만들어지고, 경계가 어디인지는 세대마다 다시 말한다.