닫힘은 값을 치르면 얻을 수 있다

1. 두 짝수

1954년 여름, 프린스턴 고등연구소. 그곳에는 진공관 컴퓨터 한 대가 있었다. 세계에서 처음 만들어진 컴퓨터들 가운데 하나였다. 메모리의 용량은 모두 합쳐 1,024워드. 프로그램 자체도, 처리할 수식도, 계산 도중에 생겨나는 온갖 것들도 그 안에 들어가야 했다.

스물여섯 살의 논리학자가 그 기계에 넣을 프로그램을 하나 짰다. 이름은 마틴 데이비스였다.

당시 컴퓨터는 거의 모두 수를 계산했다. 이 프로그램은 수 대신 문장을 판정했다. 정수에 관한 문장 하나를 건네면, 미리 정해 둔 규칙을 한 단계씩 따라갔다. 바탕에 놓인 판정 알고리즘은 저장 공간에 제한이 없는 이상적인 기계라면 언젠가는 멈추고 옳은 답을 낸다고 보장했다. 다만 실제 기계에서는 그 전에 메모리가 바닥날 수 있었다. 아직 ‘인공지능’이라는 말조차 생기기 전이었다.

이 프로그램이 거둔 가장 빛나는 성과는 두 짝수를 더하면 역시 짝수라는 사실을 증명한 것이었다. 훗날 데이비스 자신이 그렇게 썼다.

자조 섞인 말이지만 과장은 조금도 없었다. 방 하나를 차지하는 기계가 가장 잘해 냈다는 일이 초등학생도 아는 사실의 증명이었다.

곧 두 가지 물음이 따라온다. 수학의 그 많은 영역 가운데 왜 하필 이 작은 부분만은 기계에 마음 놓고 맡길 수 있을까. 기계가 참이라고 하면 반드시 참인 까닭은 무엇일까. 판정할 수 있다면서, 그토록 잘해 낸 결과가 왜 고작 이것일까. 뒤의 물음에는 기계 자체가 곧 답을 내놓았다. 그 자조보다 훨씬 무거운 답이었다. 앞의 물음에 대한 답은 25년 전 바르샤바에 있었다.

1929년 9월 24일 화요일, 오전 10시 30분. 바르샤바에서 열린 제1회 슬라브 국가 수학자 대회 이틀째였다. 제1분과 첫 발표 순서가 아직 석사 학위도 받지 못한 학생에게 돌아갔다. 바르샤바 대학교에서 수학을 공부하던 스물네 살의 프레스버거였다.

그 대회 풍경을 잠깐 들여다볼 만하다. 개막 때 프렝켈은 칸토어에 관해 강연했고, 타르스키는 혼자 두 차례 발표했다. 참석자는 대부분 폴란드인이었지만 일본에서 온 사람도, 미국 텍사스에서 온 사람도 있었다. 논문집에는 유럽의 다섯 언어로 글을 실을 수 있었고, 가장 흔한 언어는 독일어와 프랑스어였다. 대회가 끝나자 일행은 침대열차를 타고 포즈난으로 옮겨 갔다. 그곳에서는 쿠라토프스키가 위상수학 강연을 이어 갔다.

그날 프레스버거가 발표한 내용은 나중에 논문집에 실렸다. 본문 열 쪽에 쪽번호가 없는 보충문 한 쪽이 딸려 있었다. 제목을 풀면 ‘덧셈을 유일한 연산으로 삼는 정수 산술 체계의 완전성에 관하여’라는 뜻이다. 논문 첫머리에는 눈에 잘 띄지 않는 각주가 하나 있다. 결과를 얻은 때는 1928년 5월이며, 문제를 제안한 사람은 타르스키라는 내용이다.

이 문제에는 배경이 있었다. 당시 힐베르트와 그를 따르는 수학자들은 훨씬 큰 물음을 붙들고 있었다. 주어진 일차 논리식이 보편타당한지 판정하는 하나의 통일된 기계적 방법이 있는가. 이름도 붙어 있었다. 판정 문제. 컴퓨터가 없던 시절이니, 기계적 방법이란 종이에 적어 놓은 규칙을 뜻했다. 수학을 전혀 모르는 사람이라도 그대로만 따라 하면 올바른 답에 이를 만큼, 해석의 여지가 없는 규칙이었다. 힐베르트 진영은 수학 전체에 그런 규칙을 마련하고 싶었다.

타르스키는 그 문제에서 아주 작은 조각을 떼어 학생에게 맡겼다. 프레스버거가 가져온 답은 이랬다. 이 부분에는 있습니다. 정수 산술의 작은 한 영역에서는 모든 문장의 참과 거짓을 가릴 수 있다. 어떤 문장을 주든 유한 번의 단계를 거쳐 답을 내놓는, 하나의 통일된 방법도 있다. 25년 뒤 데이비스가 진공관 속에 넣은 것이 바로 그 방법이었다. 기계는 실제로 만들어질 수 있게 되기도 전에 종이 위에서 먼저 완성되어 있었다.

앞선 몇 편에서 다룬 것은 거의 모두 그 반대의 이야기였다. 집합론에서는 모순이 터졌고, 기초를 둘러싼 논쟁은 20년을 끌었다. 공리를 프로그램에 따라 나열할 수 있는 산술은 충분히 강하기만 하면 무모순이면서 동시에 완전할 수 없다는 정리까지 나왔다. 그런데 여기서는 한 학생이 사람들로 가득 찬 강의실에서 열 쪽짜리 논문으로 그런 일이 전혀 일어나지 않는 산술의 한 영역을 내놓았다. 결과를 얻은 것은 1928년, 대회에서 발표한 것은 1929년이었다. 그 정리가 출판된 1931년보다 각각 3년, 2년 앞섰다.

그러니 이렇게 물어볼 만하다. 산술은 얼마나 약해져야 완전할 수 있고, 모든 문장을 처리하는 기계까지 가질 수 있을까. 답은 곱셈을 없애면 된다는 말보다 훨씬 복잡하고, 훨씬 흥미롭다.

2. 말할 수 없는 것들

3원짜리와 5원짜리 동전만 가지고 어떤 금액을 정확히 만들 수 있을까. 11원은 만들 수 있다. 7원은 만들 수 없다. 그렇다면 어느 금액을 넘어서면 더는 만들 수 없는 금액이 나오지 않을까. 답은 그렇다. 8원부터는 모두 만들 수 있다.

프레스버거의 언어로는 이 문장들을 모두 말할 수 있다. 모두 판정할 수도 있다.

그가 다룬 것은 덧셈만 있는 정수 산술이었다. 그 언어에는 더하기 기호, 0과 1, 등호와 대소 관계, 그리고 ‘존재한다’, ‘모든’ 같은 말이 있다. 어떤 수의 세 배도 얼마든지 말할 수 있다. 그 수에 자기 자신을 두 번 더하면 그만이다. 프레스버거는 공리를 나열하면서 이미 못 박아 두었다. 곱셈 기호가 없으므로 이런 표기는 정해진 횟수만큼 덧셈을 되풀이한다는 뜻으로 읽어야 한다고. 몇 수를 더하면 다른 수와 같다는 말, 한 수가 다른 수보다 얼마만큼 크다는 말, 어떤 수를 7로 나눈 나머지가 3이라는 말, 여러 정수가 이런 조건들을 동시에 만족한다는 말. 전부 표현할 수 있고 전부 판정할 수 있다. 무언가를 부수고 남은 잔해가 아니다. 작지만 온전한 세계다.

빠져 있는 것은 두 변수를 서로 곱하는 연산이다. 그래서 그 언어로는 아예 할 수 없는 말들이 있다. 한 수가 다른 두 수의 곱이라는 말. 어떤 수가 제곱수라는 말. 어떤 수가 소수라는 말. 한 수가 다른 수의 약수라는 말, 두 수가 모두 변수일 때의 이야기다.

‘말할 수 없다’는 말의 무게는 여기에 있다. 증명하기 어렵다는 뜻이 아니다. 그 성질을 일반적으로 표현할 문장 자체가 없다는 뜻이다. 이 언어로 골라낼 수 있는 수들의 집합은 매우 가지런한 모양을 띤다. 충분히 멀리 가면 일정한 주기로 같은 패턴이 되풀이된다. 제곱수와 소수는 그렇게 늘어서지 않으므로, 그 세계에서는 이름조차 붙일 수 없다. ‘이 수는 소수인가?’ 수론에서 가장 오래된 부류에 드는 이 물음을 프레스버거의 세계에서는 꺼낼 수조차 없다.

잃은 것은 표현력이지 증명력이 아니다. 둘은 같은 것이 아니다.

여기서 세 단어를 구별해야 한다. 뒤로 갈수록 이들은 서로 다른 길을 간다. 완전하다는 것은 그 언어의 모든 문장에 대해 이론이 어느 쪽인지를 결정해 준다는 뜻이다. 17편에서 만난 것처럼 증명할 수도 반박할 수도 없는 문장이 나오지 않는다. 결정 가능하다는 것은 별개의 성질이다. 그 언어의 문장을 무엇이든 하나 주면 유한 번의 단계를 거쳐 반드시 멈추고 올바른 답을 내놓는, 통일된 기계적 방법이 있다는 뜻이다.

둘 사이에는 짧은 다리가 놓여 있다. 어떤 이론이 완전하고 그 공리들을 하나씩 유효하게 열거할 수 있다고 하자. 그러면 증명들도 하나씩 열거할 수 있다. 문장을 하나 받으면 증명들을 차례로 나열하면서 그 문장과 그 부정 중 어느 것이 먼저 나오는지 기다리면 된다. 이론이 완전하므로 둘 중 하나는 반드시 나온다. 따라서 이 과정은 끝난다. 프레스버거는 원문 첫머리에서 바로 이 점을 명시했다. 완전성 증명이 지닌 유효한 성격 덕분에, 그 증명은 문장의 참과 거짓을 가리는 방법도 함께 준다는 것이다. 증명 하나를 내놓았더니 기계 한 대가 따라 나온 셈이다.

완전하다는 말에는 한 겹이 더 있다. 그 이론이 모든 것을 안다는 뜻은 아니다. 그 언어로 말할 수 있는 것이라면 모두 결정해 준다는 뜻일 뿐이다. 말할 수 없는 것은 물을 수도 없다. 그러므로 적게 말하는 체계일수록 완전하기가 쉽다. 칭찬처럼 들리지만, 사실은 청구서의 첫 줄이다.

세 번째 단어는 실행 가능성이다. 방법이 있다는 것과, 사람이 감당할 시간과 메모리와 기계로 그 방법을 실제 돌릴 수 있다는 것은 다르다. 앞의 두 성질이 논리의 문제라면, 세 번째는 거기서 더 나아가 복잡도와 실제 자원을 묻는다. 메모리가 1,024워드뿐인 기계가 곧 이 차이를 눈앞에 들이밀게 된다.

3. 단어 하나를 지우다

그 기계의 핵심 방법은 양화사 제거라고 한다. 프레스버거 산술에서는 보통 고정된 수를 법으로 하는 합동 술어나 고정된 수로 나누어떨어짐을 나타내는 술어를 더해 언어를 먼저 확장한다. 그런 다음 이 동등한 확장 안에서 양화사를 없앤다.

문장에는 ‘어떤 수가 존재한다’거나 ‘모든 수에 대하여’ 같은 말이 들어갈 수 있다. 양화사를 제거한다는 것은 그 수가 무엇인지 맞혀 보는 일이 아니다. 문장 전체를 뜻은 정확히 같으면서도 더는 그 수를 언급하지 않는 문장으로 바꾸는 일이다.

가장 간단한 예를 보자. 자기 자신을 더하면 주어진 수가 되는 정수가 있을까. 이 문장에는 ‘그런 정수가 있을까’라는 부분이 있다. 그것을 없애면 주어진 수에 관한 조건만 남는다. 그 수가 짝수라는 조건이다.

이것이 전부다. ‘자기 자신을 더하면 그 수가 되는 정수가 존재한다’가 ‘그 수는 짝수다’로 바뀐다. 뒤의 문장은 찾아야 할 정수를 더는 언급하지 않고, 그 자리에서 확인할 수도 있다. 프레스버거의 논문에도 이런 작은 예가 나온다. ‘존재한다’가 붙은 덧셈 방정식을, 나머지와 다른 수들에 관한 조건으로 고쳐 쓴다. 데이비스의 기계가 가장 자랑스러워한 결과 역시 짝수에 관한 것이었다. 진공관 속에서 진행된 것도 바로 이런 바꿔 쓰기의 연속이었다.

다른 세계의 예도 하나 보자. 제곱하면 주어진 수가 되는 실수가 있을까. 양화사를 없애고 나면 조건 하나가 남는다. 주어진 수가 0보다 크거나 같아야 한다. 찾고 있던 수는 사라지고, 주어진 수에 관한 문장만 남았다.

이 작업을 되풀이하면 자유변수가 하나도 없는 문장은 마침내 참과 거짓을 바로 가릴 수 있는 조건으로 바뀐다. 판정 절차는 이렇게 만들어진다. 타르스키의 돌파구는 같은 발상을 실수의 다항식 등식과 부등식으로 이루어진 세계까지 밀고 들어간 데 있었다. 그곳에는 덧셈도 곱셈도 대소 관계도 양화사도 있다. 그런데도 양화사를 없앨 수 있다.

그 한 걸음에 학문 하나가 함께 들어왔다. 기하학이었다. 타르스키가 말한 초등기하학은 좌표를 도입해 실수 대수의 식으로 옮길 수 있는 문제들을 가리킨다. 직교좌표계를 하나 고정하고 점을 실수 좌표로 나타내면, 거리나 한 직선 위에 있음, 수직이나 원에 관한 관계를 유한 개의 다항식 등식 또는 부등식으로 바꿀 수 있다. 그러면 해당 기하 명제들도 기계의 처리 범위 안에 들어온다. 임의의 점집합이나 임의의 함수에 관한 일반적인 명제까지 포함되는 것은 아니다. 범위를 정하는 것은 선택한 언어이지 ‘기하학’이라는 학문 이름이 아니다.

생각해 보면 이것은 당연히 되리라 기대할 일이 아니다. ‘존재한다’는 말은 무한히 넓은 범위를 뒤져 보라는 주문처럼 보인다. 기계는 무한히 많은 수를 하나씩 살필 수 없다. 찾는 수가 없으면 영원히 멈추지 못하기 때문이다. 그 말을 없앤다는 것은 끝없는 탐색을 유한하고 곧바로 확인할 수 있는 문장으로 바꾼다는 뜻이다. 왜 하필 이 작은 영역을 기계에 맡길 수 있을까. 답의 절반은 여기에 있다. 그 안의 ‘존재한다’를 하나도 남김없이 없앨 수 있기 때문이다. 바꿀 수 있느냐 없느냐는 그 세계의 구조가 얼마나 가지런한가에 달려 있다. 가지런한 곳에서는 바뀌고, 그렇지 않은 곳에서는 바뀌지 않는다.

그것이 건네는 것은 답이지 이해가 아니다. 바꿔 쓴 결과는 엄청나게 커질 수도 있고, 사람이 아름답다고 여길 만한 증명의 모습을 갖추지 못할 수도 있다. 그러나 참과 거짓을 알려 주는 것보다 훨씬 큰 쓸모가 하나 더 있다. ‘존재한다’와 ‘모든’이 들어간 말이 그 세계 안에서 결국 어떤 대상들을 골라내는지 드러내 준다는 것이다. 훗날 모형론이 양화사 제거의 가장 중요한 가치로 받아들인 것은 바로 이 구조에 관한 정보였다.

4. 경계는 어디에 있는가

곱셈을 지운 대가로 기계 한 대를 얻을 수 있다면, 한 번 더 물어보자. 경계는 곱하기 기호에 있는가.

그렇지 않다. 서로 다른 방향에서 이 짐작을 깨뜨리는 예가 이미 두 개 있다. 첫째는 스콜렘 산술이다. 자연수에서 곱셈만 남기고 덧셈을 없애도 여전히 결정 가능하다. 둘째는 더 강력하다. 타르스키가 다룬 실수다. 덧셈과 곱셈이 모두 있고 대소 관계까지 있는데도 이 이론은 결정 가능하다.

덧셈만 있는 쪽도 얌전하고, 곱셈만 있는 쪽도 얌전하다. 정수 위에서 둘이 만나는 순간에야 성질이 달라진다.

까닭은 기호 목록에 있지 않다. 정수의 덧셈과 곱셈을 한데 모으면 대단히 풍부한 부호화를 만들 수 있다. 유한한 수열도, 증명도, 한 단계씩 진행되는 계산도 전부 정수들 사이의 관계로 고쳐 쓸 수 있다. 17편의 부호화가 필요로 했던 힘이 바로 이것이다. 프레스버거 산술은 이 일을 감당하지 못한다. 그 안에서는 두 변수를 곱하는 것조차 정의할 수 없기 때문이다. 그러므로 이 산술이 문턱 아래에 머무는 이유는 17편의 세 조건 가운데 세 번째에 있다. 무모순성 조건이나 유효하게 공리화할 수 있다는 조건을 피한 것이 아니라, 표현력의 문턱을 넘지 못한 것이다.

타르스키 자신도 책에서 이 대조를 아주 분명하게 적었다. 보통의 정수 덧셈과 곱셈 산술에 속한 관련 문장들을 모두 담을 만큼 강한 이론에는, 이런 통일된 판정법이 존재할 수 없다고.

그는 경계를 가늠하는 멋진 실험도 했다. 실수를 다루는 그 언어 안에서는 ‘이 수는 정수다’라는 성질을 일반적으로 정의할 수 없다. 그런데 변수의 범위를 곧바로 정수로 제한할 수 있게 하면, ‘한 수의 세제곱과 다른 수의 세제곱을 더한 값이 세 번째 수의 세제곱과 같아지는 정수해가 있는가’ 같은 문제가 언어 안으로 들어온다. 정수 산술도 함께 스며들어 통일된 판정법을 더는 지킬 수 없게 된다. 식은 그대로인데 변수의 범위를 실수에서 정수로 바꾸는 것만으로 논리적 운명이 통째로 달라진다.

어렵고 쉬움을 가르는 것은 기호가 아니다. 변수를 어디에서 움직이게 하느냐다.

훗날 문턱 너머의 사정이 확정되었을 때, 그 일을 한 사람들 가운데 낯익은 얼굴이 있었다. 힐베르트가 1900년에 내놓은 문제 목록의 열 번째는 이랬다. 정수 계수를 가진 임의의 다항방정식이 주어졌을 때, 정수해가 있는지 판정하라. 바로 변수를 서로 곱하며 그 값은 정수로 한정하는 문제다. 마틴 데이비스는 대학원생 시절부터 평생 이 문제를 놓지 못했다. 1954년 여름 프린스턴에서 문턱 이쪽의 기계를 진공관 속에 구현할 무렵, 그는 이미 수년째 문턱 저쪽에서 답을 찾고 있었다.

데이비스는 퍼트넘, 줄리아 로빈슨과 함께 십수 년에 걸쳐 그쪽 길을 닦았다. 마지막 조각은 마티야세비치가 채웠다. 마티야세비치는 그날을 똑똑히 기억했다. 1970년 1월 29일 레닌그라드에서 처음으로 이 해답을 공개 발표했고, 청중 가운데는 체이틴(Tseitin)도 있었다. 답은 일반적인 방법이 없다는 것이었다. 한 사람이 문턱 이쪽에서는 기계를 만들고, 저쪽에서는 그 기계를 만들 수 없다는 증명에 힘을 보탰다.

그러니 문턱은 반듯한 선 하나가 아니다. 1936년 처치와 튜링은 일반적인 일차 논리에 통일된 판정법이 없음을 증명했다. 수학 전체를 향했던 힐베르트의 소망은 이로써 무너졌다. 그러나 문턱 아래에 자리 잡은 것들은 전혀 다른 방향에서 모여들었다. 선형 산술, 실수의 대수, 대수적으로 닫힌 체, 나중에는 오토마타를 통해 다루게 된 수많은 구조가 있었다. 이들이 결정 가능한 이유도 제각각이었다. 순서 덕분인 것도, 대수적 닫힘 덕분인 것도, 오토마타나 양화사 제거 덕분인 것도 있었다. 1950년 트라흐텐브로트는 유한한 구조만 살펴보더라도 일반적인 판정 문제는 풀 수 없다는 것을 증명했다. 그리하여 논리학의 역사에 남은 것은 결정 가능에서 결정 불가능으로 넘어가는 직선이 아니라 지도 한 장이었다. 한쪽에서는 가장 큰 결정 가능 영역을 찾고, 다른 쪽에서는 가장 작은 결정 불가능 확장을 찾는 지도였다.

5. 바르샤바와 출판되지 못한 책

프레스버거는 변두리에 홀로 떨어져 있다가 우연히 논문 한 편을 쓴 학생이 아니었다. 당시 바르샤바는 유럽에서 논리학자가 가장 밀집한 곳 가운데 하나였다. 더 큰 틀에서는 르부프·바르샤바 학파에 속했다. 트바르도프스키가 토대를 놓았고, 두 세계대전 사이에는 아이두키에비치, 코타르빈스키, 레시니에프스키, 우카시에비치, 타르스키가 대표적인 인물이었다. 이 학파의 전성기는 폴란드가 다시 나라를 세운 때부터 전쟁이 터질 때까지, 두 전쟁 사이의 21년과 겹친다. 그동안 논리학은 차츰 학파의 가장 두드러진 분야가 되었다. 시선을 바르샤바의 논리학계로 좁히면 중심에는 우카시에비치, 레시니에프스키, 타르스키가 있었고, 그 주위에는 린덴바움, 프레스버거, 그리고 수많은 학생이 있었다.

프레스버거는 그 모임에서 실제로 일을 맡아 하던 사람이었다. 우카시에비치의 수리논리학 강의록도 그가 구술 강의를 받아 정리한 것이다.

출판의 연결망도 촘촘했다. 폴란드 수학계에는 《수학의 기초》 같은 전문 학술지가 있었고, 르부프와 크라쿠프에도 각각 다른 학술지가 있었다. 이들과 빈의 학자들이 서로 떨어진 섬에 살았던 것도 아니다. 타르스키는 1930년 빈을 방문했고, 같은 해 카르나프는 바르샤바로 왔다. 1935년에는 타르스키가 다시 빈에 갔다. 15편과 17편에 나왔던 빈의 이름들과 여기 나오는 바르샤바의 이름들은 그 시절 하나의 연결망 안에 있었다.

하지만 훗날의 논문 데이터베이스만 보면 타르스키 개인이 처했던 사정은 통째로 사라진다. 태어났을 때 그의 성은 타이텔바움이었다. 1923년 그는 형제와 함께 성을 타르스키로 바꾸고 가톨릭으로 개종했다. 정작 그 자신에게는 종교적 믿음이 없었다. 이유는 하나가 아니었다. 그는 폴란드인이 되고 싶었고, 당시 폴란드에서 유대인이 대학의 자리를 얻기란 매우 어렵다는 것도 알았다. 1924년 바르샤바에서 박사 학위를 받은 뒤에도 오랫동안 중등학교에서 수학을 가르쳤다. 바르샤바 대학교에서는 작은 교직 하나만 맡고 있었다. 1939년 르부프의 교수직에 지원했지만 뜻을 이루지 못했다. 그 시절 세계 최고 수준의 논리학 성과들 가운데 일부는 중등학교 교사를 겸하던 사람에게서 나왔다.

실수 대수의 판정법을 찾아낸 것은 1930년이었다. 책 끝의 역사적 주석을 보면 연대는 조금 더 거슬러 올라간다. 일부 결과는 이미 1926년부터 1928년까지의 강의에 등장했다. 그 무렵 타르스키의 강의실에 앉아 있던 바르샤바 학생들은 이 내용의 일부를 들었다. 강의실 밖 사람들은 글로 읽기까지 20년을 더 기다려야 했다.

그 뒤로는 책 자체의 여정이 시작된다. 원래 1939년 파리의 한 출판사에서 낼 예정이었지만 전쟁이 가로막았다. 원고를 다시 집어 든 곳은 미국의 연구기관이었다. 1948년 미 공군의 랜드 계획이 판정 문제에 관심을 보이면서, 9년 동안 묵혀 있던 원고가 다시 나왔다. 매킨지가 정리와 수정에 참여했고, 책은 랜드의 번호 붙은 보고서 한 권으로 인쇄되었다. 1951년 5월에는 개정판이 나왔으며, 나중에는 보통 이 1951년 판으로 인용하게 되었다. 1948년 초판이 나온 뒤 7, 8년이 지나면, 바로 그 기관의 컴퓨터에서 또 다른 정리 증명 프로그램이 돌아가게 된다.

타르스키가 방법을 찾아낸 때부터 책이 국제적으로 유통될 수 있는 형태로 세상에 나오기까지 18년이 걸렸다. 1939년 이후 왜 멈췄는지는 분명하다. 전쟁 때문이다. 그런데 그에 앞선 1930년부터 1939년까지의 9년 동안 왜 출판되지 않았는지는, 아직 설명을 찾을 수 없다.

이 대목에 등장한 연도는 모두 확인할 수 있다. 단 하나의 연도만 빼고.

프레스버거는 1904년 12월 27일 바르샤바에서 태어났다. 1923년 중등학교를 마치고 바르샤바 대학교에 들어갔다. 그 개인을 전적으로 다룬 연구는 지그문트가 1991년에 쓴 전기 한 편뿐이다. 주된 근거는 바르샤바 대학교에 남아 있던 학생 기록이었다. 그 기록들은 나중에 고해상도로 스캔되어 정리·공개되었다. 등록 서류, 수강 과목, 졸업 문서가 들어 있다. 1930년 10월 그가 수학 석사 학위를 받았다는 사실은 오늘도 한 장씩 넘겨 가며 확인할 수 있다.

그다음부터 기록은 끊긴다. 폴란드 유대인이었던 그는 나치의 홀로코스트로 목숨을 잃었다. 보통 1943년 무렵으로 추정한다. 전문 연구자가 쓴 전기에서도 그 연도 뒤에는 물음표가 붙어 있다. 정확히 언제 어디서 죽었는지, 마지막에 어떤 일을 겪었는지는 학생 시절 기록만큼 확실하게 알 수 없다.

한 사람이 이십 대에 쓴 열 쪽은 70년 넘게 기계에서 기계로 옮겨 가며 실행되었다. 그러나 그 사람이 어떻게 죽었는지는 쓸 수 없다.

6. 다른 길

1954년 여름의 그 기계로 돌아가자.

판정법도 있고 기계도 있었다. 하지만 데이비스는 곧 벽에 부딪혔다. 종이 위에서는 몇 단계에 불과하던 방법을 기계로 옮기려면, 먼저 수식을 정해진 표준 형태로 바꿔야 했다. 바꿔 쓰는 동안 식은 부풀어 올랐다. 조건과 조건의 조합이 겹겹이 쌓여, 처음에는 길지 않던 한 줄이 몇 배나 길어질 수 있었다. 1,024워드의 메모리는 이내 모자랐다. 훗날 더 복잡한 판정 프로그램에 그가 별 기대를 걸지 않게 된 출발점이 여기였다.

이 기계는 처음으로 눈앞에 보여 주었다. 판정할 수 있다는 것과 그 판정 비용을 감당할 수 있다는 것은 다르다는 사실을.

2년 뒤에는 반대쪽에서 출발한 사람들이 있었다. 랜드의 뉴얼과 쇼, 카네기 공과대학의 사이먼은 논리 정리를 증명하는 프로그램을 만들었다. 대상은 화이트헤드와 러셀의 《수학 원리》 앞부분에 실린 명제들이었다. 이 프로그램은 결과를 보장하는 규칙을 끝까지 따라가지 않았다. 골라 가며 찾았다. 목표에 더 가까워 보이는 길부터 가고, 갈래가 너무 많으면 일부를 잘라 냈다. 찾으면 증명을 내놓았다. 못 찾으면, 못 찾았다고 할 수 있을 뿐이었다. 찾지 못했다는 말과 존재하지 않는다는 말 사이에는 데이비스의 기계에는 있고 이 프로그램에는 없는 것이 놓여 있었다. 보장. 당시 ‘인공지능’이라는 이름이 생긴 지는 채 1년이 되지 않았다.

한쪽은 답을 보장했지만 메모리가 금세 터져 나갔다. 다른 쪽은 메모리가 터지는 일을 피하려고, 언제나 증명을 찾아낸다는 보장을 내려놓았다. 물론 찾아낸 증명은 여전히 건전한 추론 규칙을 따라야 했다. 두 길은 여기서 갈라졌다.

그 갈림길에 중국인 한 사람이 서 있었다. 왕하오는 1921년 지난에서 태어나 쿤밍의 시난연합대학을 졸업한 뒤, 미국으로 건너가 수리논리학을 연구했다. 1958년 여름, 그는 뉴욕주 포킵시의 IBM 연구소에서 당시의 대형 컴퓨터로 프로그램 몇 개를 짰다. 그중 하나는 《수학 원리》의 앞 다섯 장에 있는 200여 개 정리를 빠짐없이 증명했다. 걸린 시간은 모두 합쳐 약 37분. 그중 13분의 12는 입력을 읽고 결과를 인쇄하는 데 쓰였고, 실제 증명에 쓴 시간은 3분도 되지 않았다.

왕하오는 이 결과들을 논문으로 썼다. 제목은 ‘기계화된 수학을 향하여’라는 뜻이었다. 힐베르트 진영이 품었던 소망을 달리 표현한 것처럼 들린다. 논문에는 꽤 날 선 대목이 있다. 뉴얼 일행이 휴리스틱과 알고리즘을 비교하면서 대조군으로 내세운 것은 유난히 둔한 알고리즘이었다. 특별히 비효율적인 알고리즘을 골라 놓고 휴리스틱이 알고리즘보다 낫다고 주장하는 것은, 공정한 비교라고 보기 어렵다는 지적이었다.

그는 결과에서 교훈 하나를 더 끌어냈다. 상당히 풍부한 영역에서도 실제로 증명되는 정리 대부분은 그 영역이 지닌 힘 가운데 아주 작은 부분만 쓴다는 것이다. 적게 말하는 것은 기계가 판정할 수 있기 위한 전제다. 그런데 사람이 정말로 증명하려는 것들은 대개 처음부터 그 힘을 조금만 써도 된다.

1983년 왕하오는 기계 정리 증명 분야의 첫 ‘마일스톤 상’을 받았다. 상을 제정한 곳은 국제 인공지능 공동회의였다. 그로부터 거의 20년 뒤, 데이비스가 이 초기 역사를 글로 정리했을 때 제목 아래에는 이런 말이 적혀 있었다. 왕하오를 기리며.

7. 비용은 별도다

갈라진 두 길은 각자 거의 20년을 더 갔다.

휴리스틱을 택한 쪽에서는 프로그램이 점점 많아지고 약속도 점점 커졌다. 1973년 영국 과학연구위원회는 응용수학자 라이트힐에게 인공지능 전반을 평가해 달라고 의뢰했다. 그의 보고서에는 한 표현이 되풀이되었다. 조합 폭발. 작고 깔끔한 문제에서는 프로그램이 뛰어난 성능을 보였다. 하지만 현실 세계의 규모로 넓히면 살펴봐야 할 가능성이 걷잡을 수 없이 늘어, 끝내 다 돌아볼 수 없었다.

이듬해, 다른 쪽에서는 더 차가운 소식이 나왔다. 1974년 피셔와 라빈이 물은 것은 프레스버거의 방법이 빠르냐가 아니었다. 어떤 방법이든 근본적으로 훨씬 빨라질 수 있느냐였다. 답은 아니었다. 이 산술에 대해 누가 어떤 일반적인 방법을 고안하더라도, 이런 식들이 반드시 있다. 입력이 조금 더 길어질 때마다 필요한 단계 수가 한 번씩 제곱되는 식들이다. 이를 이중 지수 하한이라고 한다. 1978년 오펜은 상한도 제시했다. 문제는 몹시 높은 위아래 두 벽 사이에 놓이게 되었다.

그 길이의 모든 식이 그만큼 어렵다는 뜻은 아니다. 어떤 일반적인 방법을 짜더라도 그런 나쁜 입력이 있다는 뜻이다. 누군가 프로그램을 서툴게 짠 탓도 아니다. 문제 자체의 성질이다. 피셔와 라빈은 증명의 길이도 함께 논했다. 적절한 조건 아래에서, 증명 가능한 문장 가운데도 증명 자체가 극도로 길 수밖에 없는 것들이 있다. 이리하여 결정 가능하다는 것, 증명 가능하다는 것, 사람이 끝까지 읽을 수 있는 증명을 실제 손에 넣는다는 것이 다시 세 가지로 갈라졌다.

두 길은 같은 벽 앞에서 다시 만났다. 라이트힐이 말한 것은 한 분야가 현실 세계의 규모에 다다랐을 때 부딪힌 벽이었다. 피셔와 라빈이 말한 것은 이랬다. 가장 작고 가장 깔끔하며 가장 확실하게 보장된 산술의 한 조각으로 물러나도, 그 벽은 거기에 있다.

실수 쪽에서도 같은 이야기가 되풀이되었다. 타르스키의 방법은 판정법이 존재함을 증명했지만, 실제로 돌릴 만한 알고리즘은 아니었다. 실용적으로 실행할 수 있는 최초의 완전한 방법은 보통 1975년 콜린스의 것으로 꼽는다. 다차원 실수 공간을 유한 개의 영역으로 나누되, 입력된 다항식 각각의 부호가 한 영역 안에서는 변하지 않게 한다. 그러면 무한히 많은 점에 관한 문제가 각 영역의 대표 점에서 판정하는 유한한 문제로 바뀐다. 훗날 컴퓨터 대수 시스템의 토대가 된 방법이다. 그러나 변수의 개수가 늘어나면, 나뉜 영역의 수는 이중 지수로 커질 수 있었다. 1988년 대븐포트와 하인츠는 이것이 그 방법만의 잘못은 아니라는 것을 증명했다. 실수 위의 일반적인 양화사 제거 자체에 그 정도의 어려움이 있었다. 그 뒤 수십 년에 걸친 개선의 주된 방향은 그 하한을 뒤집는 것이 아니라 쓸데없는 일을 덜 하는 데 있었다. 더 나은 사영을 쓰고, 지금 푸는 문제에 정말 필요한 영역만 나누는 것이다.

기하학 쪽에서는 다른 방식으로 값을 치른 사람이 있었다. 1976년에서 1977년 사이, 우원쥔은 베이징에서 기하 정리의 증명을 컴퓨터로 옮기기 시작했다. 훗날 한 서문에서 그는 타르스키의 기계화 정리가 초등기하학을 널리 포괄하기는 하지만 효율이 너무 낮다고 썼다. 우원쥔의 방법은 기하 문제를 여러 다항식 등식으로 바꾸어 처리했다. 대소 관계가 들어가는 명제는 일단 옆에 두었다. 물을 수 있는 범위를 조금 좁히자 기계가 돌아갔다. 만만치 않은 기하 정리들이 여럿 기계로 증명되었다.

그는 이 작업에 ‘수학 기계화’라는 이름을 붙이고, 영감을 준 것은 중국 고대 수학이라고 밝혔다. 그의 눈에 《구장산술》과 서기 263년 유휘가 붙인 주석은 동양의 수학적 기계화 알고리즘 체계를 대표하는 고전이었다. 5편의 유휘를 여기서 20세기 수학자가 자신의 선배로 알아본 셈이다. 같은 서문에는 왕하오의 기계가 3분 만에 200여 개 명제를 증명한 일도 적혀 있다.

따라서 결정 가능성과 실용성 사이에는 틈이 있다. 수학에서 결정 가능하냐고 물을 때는, 언젠가는 멈추고 올바른 답을 내놓는다고 보장하는 통일된 방법이 있는지를 묻는다. 몇 초 안에 된다고 약속하지 않는다. 100년 안에 된다고도 약속하지 않는다. 심지어 이 우주가 허락하는 자원 안에서 끝낼 수 있다고도 약속하지 않는다. 공학에서 쓸 만하냐고 물을 때는, 실제로 나타나는 문제들에 대해 주어진 기계와 시간과 메모리로 유용한 결과를 대체로 빨리 내놓을 수 있는지를 묻는다. 한 물음에는 그렇다는 답이, 다른 물음에는 아니라는 답이 나올 수 있다. 실제로 자주 그렇다.

거꾸로도 마찬가지다. 최악의 경우가 끔찍하다고 해서 쓸모가 없다는 뜻은 아니다. 이론상 최악의 성능은 형편없지만 실제 처리할 문제들에서는 상당히 효과적인 판정 프로그램이 많다. 왕하오의 교훈이 여기서 다시 나온다. 실제로 마주치는 문제 대부분은 가장 나쁜 구석에 몰려 있지 않다.

8. 세 칸짜리 장부

제목으로 돌아가자. 닫힘은 값을 치르면 얻을 수 있는가. 얻을 수 있다. 실제로 두 번 얻었다. 두 번에 걸쳐 얻은 것은 서로 달랐다.

프레스버거가 얻은 것은 완전하고 결정 가능한 정수 산술의 한 조각이었다. 대신 수론의 넓은 영역을 그 안에서는 말할 수 없었다. 타르스키가 얻은 것은 실수 대수와 거기에 딸린 초등기하학의 통일된 판정법이었다. 그는 아무것도 삭제하지 않았다. 그쪽의 대가는 다른 데 있었다. 그 언어는 애초부터 ‘이 수는 정수다’라고 말할 수 없었다. 두 번 모두 시장에서 거래를 한 것은 아니다. 구체적인 수학적 대상을 연구하다가, 그 대상이 마침 매우 가지런하다는 것을 발견했다. ‘샀다’는 표현은 후대 사람이 돌아보며 붙인 비유이지, 당시 누군가 실제로 값을 지불했다는 뜻이 아니다.

이 두 결과가 가장 오래 살아남은 곳은 뒤에 자라난 두 학문이었다. 타르스키의 양화사 제거는 모형론의 기본 기술이 되었고, 실수와 대수적으로 닫힌 체는 모형론 교과서의 가장 기본적인 예가 되었다. 프레스버거 산술은 프로그램 검증으로 들어갔다. 프로그램이 올바른지는 흔히 배열의 첨자, 반복문의 횟수, 정수들 사이의 선형 관계에 달려 있다. 바로 이 산술이 잘 다루는 문장들이다. 1972년 쿠퍼는 프레스버거의 방법을 컴퓨터에서 실용적으로 쓸 수 있게 고쳤다. 논문 제목은 ‘곱셈 없는 산술에서 정리를 증명하기’였고, 《기계 지능》이라는 총서에 실렸다. 오늘날 수학자의 증명을 한 줄씩 검사해 주는 프로그램 가운데는 ‘프레스버거 산술의 판정 절차’라는 이름의 전용 모듈을 갖춘 것도 있다. 그 안에 들어 있는 것이 쿠퍼의 이 방법이다.

그러면 여기서 무엇을 가져갈 수 있을까.

어떤 체계가 자기 언어로 말할 수 있는 모든 문장에 답을 준다. 대단한 능력처럼 들린다. 그러나 그것은 동시에 그 체계가 말할 수 없는 것들을 적어 놓은 목록이기도 하다. 어떤 설명 체계를 가늠할 때는 답하지 못하는 물음부터 세고, 그다음에 답할 수 있는 물음을 세어야 한다. 모든 물음에 답하는 체계는 대개 묻는 것이 너무 적다.

1954년의 그 기계 이래, 질문에 답하려고 만든 기계는 모두 같은 장부에 적을 수 있다. 장부에는 세 칸이 있다. 무엇을 물을 수 있는가. 답에 보장이 붙는가. 답을 한 번 얻는 데 얼마의 대가를 치러야 하는가.

프레스버거의 열 쪽이 말한 것은, 물을 수 있는 것의 칸을 충분히 좁히면 보장의 칸을 채울 수 있다는 사실이다. 타르스키가 책에 적은 말과 1936년 처치와 튜링의 결과는, 물을 수 있는 범위를 정수의 덧셈과 곱셈까지 넓히는 순간 보장의 칸을 더는 가득 채울 수 없다고 말한다. 피셔와 라빈이 말한 것은 그다음이다. 물을 수 있는 것을 프레스버거만큼 좁히고 보장의 칸도 채웠더라도, 비용의 칸에는 여전히 감당할 수 없는 청구서가 들어올 수 있다.

데이비스의 기계는 보장의 칸을 채우고 비용의 벽에 부딪혔다. 1956년의 프로그램은 보장의 칸을 비워 비용을 줄이려 했다. 왕하오는 같은 영역에서 보장과 비용을 모두 해결했다. 영역이 충분히 작았기 때문이다. 우원쥔은 기하학에서 물을 수 있는 것의 한 귀퉁이를 덜어 내어 비용을 감당할 수 있게 했다. 그 뒤의 기계들은 세 칸 사이를 오갔다. 보장을 지키면서 질문의 범위를 조금씩 넓힌 것들도 있었다. 데이비스가 나중에 퍼트넘 등과 함께 만든 방법은 여러 논리 조건을 동시에 만족시킬 수 있는지 판정했고, 그 후손들은 훗날 반도체와 소프트웨어 검증에 널리 쓰였다. 물을 수 있는 범위를 한껏 열어 놓고 보장의 칸은 비워 둔 것들도 있었다. 훗날 인공지능이라고 부르게 된 것의 상당 부분은 이런 장부를 썼다.

세 칸을 한꺼번에 가득 채운 페이지는 누구도 쓰지 못했다. 그중 질문의 범위와 보장을 동시에 끝까지 채울 수 없다는 것은 정리가 말해 준다.

이 글에는 전쟁에 막혀 인쇄소 문턱을 넘지 못한 책이 있고, 전쟁 속에서 끊긴 한 사람의 생애가 있다. 원고는 나중에 되찾았지만, 프레스버거의 마지막 날들은 물음표가 붙은 연도 하나로만 남았다. 다음 편에서는 시간을 1933년으로 돌려, 어느 대학으로 돌아간다.

수의 계산은 이어진다. 그러나 무엇을 수학으로 셀 것인지는 아직 셈이 끝난 적이 없다.

사료와 더 읽을거리

아래 자료는 본문에 나오는 역사적 세부와 해석상의 차이에 대응한다. 소장 기록, 고대 문학, 현대의 재구성은 서로 같은 종류의 증거가 아니다.

• 프레스버거 원 논문의 번역과 주석
• 스탠퍼드 철학 백과사전: 타르스키
• 타르스키의 랜드 판정법 보고서
• 왕하오의 원 논문 「기계화된 수학을 향하여」
• 오펜의 1978년 복잡도 상한 논문
• 브라운과 대븐포트의 양화사 제거 복잡도 논문
• 우원쥔의 수학 기계화 총서 서문