기계가 풀 수 없는 문제

1928년 힐베르트는 물었습니다. 어떤 논리식이 주어지든 그것이 논리 법칙만으로 증명되는지를 기계적으로 가려내는 방법이 있을까? 8년 뒤 스물세 살의 튜링은 '기계적'이 무슨 뜻인지부터 정의해 답이 '없다'임을 보였고, 그 정의가 오늘날 컴퓨터의 이론적 바탕이 되었습니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 스위치, 표의 칸, 기호 단추는 눌러서 바꿀 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

두 사람이 논쟁을 벌이다 끝내 합의하지 못한다고 해 봅시다. 17세기 말 하노버 궁정의 고트프리트 라이프니츠는 그런 날이 오지 않기를 꿈꾸었습니다. 모든 개념을 기호로 적는 '보편 문자⁠(characteristica universalis)⁠'와, 그 기호를 규칙대로 다루어 결론을 끌어내는 '추론 계산⁠(calculus ratiocinator)⁠'이 있다면, 다툼은 계산 실수를 찾는 일이 됩니다. 흔히 인용되는 바에 따르면, 그는 1680년대 무렵의 글에서 논쟁하는 사람들이 그저 "계산해 봅시다(Calculemus)"라고 말하면 된다고 썼습니다. 그 꿈이 미적분⁠(calculus)⁠의 기호를 고르는 데도 영향을 주었다는 이야기는 「순간의 속도」에 있습니다.

라이프니츠는 계산하는 기계도 만들었습니다. 1673년 초 그는 곱셈과 나눗셈까지 하는 계산기의 나무 모형을 들고 런던 왕립학회를 찾았습니다. 길이가 다른 톱니를 계단처럼 붙인 원통, 곧 '계단 톱니'는 20세기의 기계식 계산기에까지 쓰였고, 그가 만든 기계 한 대가 지금도 하노버에 남아 있습니다.

기계보다 더 멀리 간 것은 0과 1이었습니다. 라이프니츠는 0과 1만으로 모든 수를 적는 이진법⁠(binary)⁠도 연구해 1703년 파리 과학 아카데미의 논문집에 발표했습니다. 이진법에서는 자리가 오른쪽부터 차례로 1, 2, 4, 8, …을 나타냅니다. 6은 4 + 2이므로 4의 자리와 2의 자리에 1을, 1의 자리에 0을 적어 110이 됩니다.

이 1703년 논문에는 『주역』 이야기도 붙어 있습니다. 베이징의 예수회 선교사 부베가 보내 준 64괘 배열이 0부터 63까지의 이진수 차례와 같다는 설명입니다. 괘는 이어진 막대(양)와 끊어진 막대(음)를 여섯 줄 쌓은 기호이니, 양을 1로, 음을 0으로 읽으면 괘 하나가 여섯 자리 이진수 하나가 됩니다. 1697년 브라운슈바이크 공작에게 보낸 편지에서는 1과 0으로 모든 수가 만들어지는 것을 무에서 만물을 짓는 창조의 형상으로 보기도 했습니다. 그보다 훨씬 앞서 기원전 몇 세기 무렵 인도의 운율학자 핑갈라는 짧은 음절과 긴 음절의 무늬를 빠짐없이 늘어놓은 표를 남겼습니다. 어떤 무늬가 그 표의 몇 번째인지 계산하는 방법은 두 종류의 음절을 0과 1로 읽는 이진법 계산과 같았습니다(「세지 않고 세기」 1절).

이 글은 라이프니츠의 꿈이 250년 뒤 정확한 질문이 되고, 그 질문에 부정의 답이 나오는 과정을 따라갑니다. 질문은 이렇습니다. 모든 수학 문제를 기계적으로 풀 수 있는가? 답을 얻으려면 먼저 '기계적'이라는 말을 정의해야 했고, 그 정의가 컴퓨터를 낳았습니다. 길은 이렇게 이어집니다. 논리를 0과 1의 계산으로 바꾸고(1절), 논리만으로 산술을 세우려다 모순을 만나고(2절), 증명할 수 없는 참을 찾고(3절), '기계'를 정의하고(4절), 그 기계가 풀 수 없는 문제를 찾습니다(5절). 그 뒤로 실제 컴퓨터(6절), 풀 수는 있지만 너무 오래 걸리는 문제(7절), 마음과 기계에 관한 논쟁(8절)이 이어집니다.

1 · 생각의 대수불의 0과 1, 섀넌의 스위치

이 절의 물음은 이것입니다. 참과 거짓을 따지는 추론을 덧셈과 곱셈 같은 계산으로 바꿀 수 있을까? 바꿀 수 있다면, 그 계산을 전선과 스위치에 맡길 수 있을까?

라이프니츠의 추론 계산을 실제로 한 걸음 해낸 사람은 영국 링컨의 구두장이 아들 조지 불이었습니다. 대학을 다니지 못하고 수학을 혼자 공부한 그는 1849년 아일랜드에 새로 세워진 퀸스 칼리지 코크의 첫 수학 교수가 되었습니다. 1854년 그곳에서 낸 책이 『사고의 법칙』입니다.

이 책에서 불은 참을 1, 거짓을 0으로 적고, '그리고'를 곱셈으로 적었습니다. 'p 그리고 q'는 둘 다 참일 때만 참인데, 곱셈도 $1 \cdot 1 = 1$이고 하나라도 0이 끼면 0이 되어 딱 맞습니다. 예를 들어 '참 그리고 거짓'은 $1 \cdot 0 = 0$, 곧 거짓입니다. '또는'은 덧셈으로 적었습니다. 다만 둘 다 참이면 1 + 1 = 2가 되어 0과 1을 벗어나므로, 불은 덧셈을 두 경우가 겹치지 않을 때만 썼습니다. 그래서 불의 '또는'은 '둘 가운데 정확히 하나'에 가깝고, 둘 다여도 참인 오늘날의 OR와는 조금 다릅니다. 이 계산을 불 대수⁠(Boolean algebra)⁠라고 부릅니다.

불 대수에는 보통의 대수에 없는 법칙이 하나 있습니다. '붉은 것'이면서 '붉은 것'인 것은 그냥 '붉은 것'이므로 $x \cdot x = x$입니다. 양변에서 $x \cdot x$를 빼면 $x - x \cdot x = 0$이고, $x$를 옮겨 묶으면 $x(1 - x) = 0$입니다. $1 - x$는 '$x$가 아닌 것'이므로, 이 식은 '$x$이면서 $x$가 아닌 것은 없다', 곧 어떤 것도 그것이면서 동시에 그것이 아닐 수는 없다는 모순율⁠(law of contradiction)⁠이 됩니다. 불은 이 식의 해가 되는 수가 0과 1뿐이라는 데 주목했습니다($x = 0$이거나 $1 - x = 0$이어야 하니까요). 정리하면, 논리는 0과 1만 있는 대수입니다.

이 대수로 덧셈을 해 봅시다. 한 자리 이진수 두 개 $A$, $B$를 더하면 답은 두 자리입니다. 0 + 0 = 00, 0 + 1 = 01, 1 + 0 = 01이고, $1 + 1 = 10_2$입니다(아래 첨자 2는 이진법이라는 표시이고, 10₂는 2입니다). 오른쪽 자리를 합의 자리, 왼쪽 자리를 올림의 자리라 부릅니다.

이 계산을 하는 부품이 게이트입니다. 게이트는 0 또는 1을 두 개 받아 0 또는 1을 하나 내보냅니다. AND는 두 입력이 모두 1일 때만, OR는 하나라도 1이면, XOR(배타적 또는)는 정확히 하나만 1일 때 1을 내보냅니다. 예를 들어 입력이 1과 1이면 AND는 1, OR는 1, XOR는 0을 냅니다. 아래 회로에서 합의 자리를 만드는 게이트를 로, 올림의 자리를 만드는 게이트를 로 골라, 입력 $A =$ , $B =$ 에 대해 맞는 답이 나오는지 보세요. 처음 상태에서는 1 + 1의 답이 틀리게 나옵니다. 게이트를 바꿔 가며 네 가지 입력 모두에서 맞는 답이 나오게 하는 것이 목표입니다.

정리하면, 덧셈이라는 산수가 AND와 XOR라는 두 논리 연산으로 바뀌었습니다. 남은 물음은 이 논리 연산을 무엇으로 만드느냐입니다.

불의 대수가 전선으로 옮겨진 것은 83년 뒤였습니다. 1937년 MIT의 대학원생 클로드 섀넌은 석사 논문에서 전화 교환기에 쓰이던 계전기⁠(relay)⁠ 스위치를 직렬로 이으면 AND, 병렬로 이으면 OR가 된다는 것을 보였습니다. 한 줄로 이은 두 스위치는 둘 다 닫혀야 전류가 흐르고, 나란히 이은 두 스위치는 하나만 닫혀도 흐르기 때문입니다. 닫힌 스위치를 1, 열린 스위치를 0, 전류가 흐르는 것을 1로 읽으면 위의 AND, OR와 똑같습니다.

남은 문제는 게이트의 출력을 다음 게이트의 입력으로 잇는 것입니다. 계전기는 전류가 흐르면 전자석이 쇳조각을 끌어당겨 다른 회로의 스위치를 닫는 부품이어서, 한 회로의 켜짐과 꺼짐이 다른 회로를 여닫게 할 수 있습니다. 그래서 게이트를 이어 붙여 반가산기 같은 회로를 만들 수 있습니다.

섀넌은 두 세계를 모두 알고 있었습니다. 그는 미시간 대학 시절 철학 강의에서 불의 논리를 배웠고, MIT에서는 전기공학자 버니바 부시가 만든 계산기 '미분 해석기⁠(differential analyzer)⁠'에 딸린, 계전기로 가득한 제어 회로를 다루고 있었습니다. 복잡한 배선도를 불 대수로 적어 간단히 줄일 수 있게 되자, 회로 설계는 손재주가 아니라 계산이 되었습니다.

이 논문은 흔히 20세기에 가장 중요한 석사 논문으로 꼽힙니다. 오늘날의 칩 안에는 수십억 개의 트랜지스터⁠(transistor)⁠가 있습니다. 트랜지스터는 전기 신호로 여닫는 아주 작은 전자 스위치이고, 이것들도 같은 원리로 AND와 OR, 그리고 0과 1을 뒤바꾸는 NOT을 만듭니다.

2 · 논리로 산술을프레게의 체계와 러셀의 편지

이 절의 물음은 이것입니다. 1, 2, 3과 덧셈 같은 산술 전체를 논리의 규칙만으로 세울 수 있을까? 그 시도는 어디서, 어떤 모순에 부딪혔을까?

불은 논리를 대수로 만들었습니다. 독일 예나 대학의 수학자이자 논리학자 고틀로프 프레게는 거꾸로 산술을 논리로 만들려 했습니다. 수와 덧셈과 수학적 귀납법⁠(mathematical induction)⁠을 논리의 법칙만으로 정의할 수 있다면, 산술의 진리는 논리의 진리가 되고 더 이상 직관이나 경험에 기댈 필요가 없습니다. 수학적 귀납법은 어떤 성질이 0에서 성립하고, 어느 수 n에서 성립하면 n + 1에서도 성립한다는 것을 보여서 모든 자연수⁠(natural number)⁠에서 성립한다고 결론짓는 증명법입니다. 첫 도미노가 넘어지고, 어느 도미노가 넘어지면 다음 것도 넘어지면, 모든 도미노가 넘어지는 것과 같습니다.

1879년 그는 100쪽이 안 되는 얇은 책 『개념 표기법』에서 형식 언어⁠(formal language)⁠를 처음으로 내놓았습니다. 형식 언어란 쓸 수 있는 기호와 기호를 잇는 문법을 빠짐없이 정해 두어, 한 문장이 두 가지로 읽힐 여지가 없게 만든 인공 언어입니다. 프레게의 언어에는 '모든'과 '어떤'을 기호로 다루는 양화사⁠(quantifier)⁠가 있었습니다. 그 덕분에 "모든 수 x에 대해 x + 0 = x이다"나 "어떤 수 x가 있어 x + x = 4이다" 같은 문장을 기호만으로 적고, 기호를 옮기는 규칙만으로 증명을 따질 수 있게 되었습니다. 오늘날 논리학 교과서의 기호 논리⁠(symbolic logic)⁠는 거의 모두 이 책에서 시작합니다. 1893년 『산술의 기본 법칙』 1권이 나왔고, 1902년에는 2권이 인쇄되고 있었습니다.

프레게의 체계에는 겉보기에 당연한 원리가 하나 있었습니다. 어떤 성질이든 그 성질을 가진 것들을 모아 집합⁠(set)⁠ 하나를 만들 수 있다는 것입니다. 성질 '짝수이다'를 고르면 짝수 전체의 집합이 생기고, 성질 '숟가락이다'를 고르면 숟가락들의 집합이 생깁니다. 1902년 6월 16일, 케임브리지 트리니티 칼리지의 버트런드 러셀이 편지를 보내 이 원리가 모순을 낳는다고 알렸습니다. 성질 "자기 자신을 원소⁠(element)⁠로 갖지 않는다"를 고르면 됩니다(러셀의 역설⁠(Russell's paradox)⁠). 칸토어의 집합론⁠(set theory)⁠ 쪽에서 본 이 이야기는 「무한에도 크기가 있다」 5절에 짧게 나옵니다. 여기서는 그 모순을 손으로 만져 봅니다.

아래 그림에서 할 일은 하나입니다. 문단 끝의 선택지를 눌러 집합 R을 두 상자 가운데 하나에 넣어 보고, 어디에 넣어도 규칙이 어긋난다는 것을 확인하는 것입니다.

먼저 두 상자를 익혀 봅시다. 숟가락들의 집합은 숟가락이 아니므로 자기 자신의 원소가 아니고, 오른쪽입니다. 반대로 '숟가락이 아닌 것들의 집합'은 그 자신도 숟가락이 아니니 자기의 원소이고, 왼쪽입니다. 이제 오른쪽 상자에 든 것 전부를 모아 집합 $R$를 만듭니다. 곧 R의 원소는 '자기 자신을 원소로 갖지 않는 집합'이고, 그런 집합만입니다. $R$도 집합이니 어느 상자엔가 들어가야 합니다. $R$을 에 넣어 봅시다.

어느 쪽에 두어도 반대쪽으로 가라는 화살표가 나타납니다. 기호로 적으면 $R \in R \iff R \notin R$입니다. ∈는 '~의 원소이다', ∉는 '~의 원소가 아니다', ⟺는 '~이면 ~이고, 거꾸로도 그렇다'로 읽습니다. 'R이 R의 원소이다'와 'R이 R의 원소가 아니다'가 서로를 뜻하니, 둘 중 어느 것도 참일 수 없습니다. 정리하면, "성질이 있으면 집합이 있다"는 원리 하나가 모순을 만든 것입니다.

이 논증은 집합이 자기 자신을 가리키게 한 뒤 그 답을 뒤집는다는 점에서 칸토어의 대각선 논법⁠(diagonal argument)⁠과 같은 모양입니다. 이 모양은 이 글에서 두 번 더 나옵니다.

당신이 모순을 발견한 일은 저를 더없이 놀라게 했고, 거의 경악하게 했다고 말하고 싶을 정도입니다. 제가 산술을 세우려던 토대가 흔들렸으니까요.— 고틀로프 프레게, 러셀에게 보낸 답장(1902년 6월 22일)

프레게는 2권에 서둘러 부록을 붙여 체계를 고치려 했지만, 그 수정도 뒤에 모순을 낳는 것으로 밝혀졌습니다. 무너진 것이 정확히 프레게의 어느 법칙이었고 그 법칙에 무엇이 숨어 있었는지는 「틀린 증명이 만든 수학」 6절에서 따로 따라갑니다.

러셀은 케임브리지 시절의 스승이던 수학자이자 철학자 앨프리드 노스 화이트헤드와 함께, 집합에 '유형'이라는 층을 두어 자기 자신을 원소로 가질 수 없게 막는 체계를 세웠습니다. 개별 대상은 0층, 대상들의 집합은 1층, 1층 집합들의 집합은 2층에 두고, 어떤 집합이든 자기보다 한 층 아래의 것만 원소로 가질 수 있게 하는 것입니다. 숟가락은 0층, 숟가락들의 집합은 1층입니다. 그러면 "자기 자신을 원소로 갖는가"라는 질문은 문법에 맞는 문장이 되지 않고, R은 처음부터 만들 수 없습니다. 그 결과가 1910년부터 1913년까지 세 권으로 나온 『수학 원리』입니다.

이 책이 얼마나 신중했는지 보여 주는 유명한 예가 있습니다. 책의 명제에는 *54.43처럼 별표가 붙은 번호가 매겨져 있습니다. 1권의 명제 *54.43 뒤에는 "산술의 덧셈이 정의되면 여기서 1 + 1 = 2가 따라 나온다"는 말이 붙어 있고, 덧셈이 실제로 정의되어 증명이 끝나는 곳은 2권의 *110.643입니다. 그 명제에는 "위 명제는 이따금 쓸모가 있다"는 건조한 논평이 달려 있습니다. 러셀의 자서전에 따르면 케임브리지 대학 출판부는 이 책에서 손해를 볼 것으로 보았고, 두 저자가 출판비 일부를 직접 댔습니다.

러셀의 삶은 논리학 밖으로도 뻗었습니다. 1차 세계대전 중 징병 반대 운동으로 1916년 트리니티 칼리지의 강사직을 잃었고, 1918년에는 반전 글 때문에 여섯 달 동안 브릭스턴 감옥에 갇혔습니다. 그는 감옥에서 『수리 철학 입문』을 썼습니다. 1950년에는 노벨 문학상을 받았고, 말년에는 핵무기 반대 운동을 이끌었습니다.

프레게의 계획은 철학의 오래된 물음, 곧 산술의 참은 어디서 오는가에 대한 대답이기도 했습니다. 쾨니히스베르크의 철학자 칸트는 『순수이성비판』(1781)에서 7 + 5 = 12를 예로 들었습니다. '7'과 '5'와 '더한다'의 뜻을 아무리 풀어도 12는 나오지 않고, 손가락 다섯 개를 하나씩 7에 보태 보는 것 같은 직관의 도움을 받아야 한다는 것입니다. 그래서 그는 산술을 경험에 앞서 알 수 있으면서도 낱말의 뜻만 풀어서는 나오지 않는 '선험적 종합 판단⁠(synthetic a priori judgment)⁠'으로 분류했습니다. 프레게는 1884년 『산술의 기초⁠(basics)⁠』에서 이에 맞섰습니다. 수의 개념을 논리만으로 정의하면 산술의 법칙은 뜻을 풀기만 해도 나오는 '분석적' 진리가 된다는 것입니다. 수학을 논리로 환원할 수 있다는 이 입장을 오늘날 논리주의⁠(logicism)⁠라고 부릅니다. 다만 프레게도 기하학만큼은 칸트처럼 공간의 직관에 기댄다고 보았습니다. 러셀의 편지는 프레게의 체계를 무너뜨렸지만 논리주의를 끝내지는 않았습니다. 러셀과 화이트헤드의 『수학 원리』가 그 계획을 이어 간 책이고, 3절의 형식주의⁠(formalism)⁠와 직관주의⁠(intuitionism)⁠는 같은 물음에 나온 다른 두 대답입니다.

3 · 결정 문제힐베르트의 꿈과 괴델의 문장

이 절의 물음은 이것입니다. 역설이 드러난 뒤, 수학이 다시는 모순에 빠지지 않는다고 확신할 방법이 있을까? 모든 참인 명제를 증명할 수 있고, 증명되는지를 기계로 가려낼 수 있는 체계를 만들 수 있을까? 힐베르트는 "그렇다"고 믿었고, 괴델은 그 믿음의 한 부분이 불가능하다는 것을 증명했습니다.

역설이 알려진 뒤 수학자들은 두 갈래로 나뉘었습니다(수학 기초론 논쟁⁠, debate on the foundations of mathematics⁠). 암스테르담의 수학자 브라우어르는 사람이 한 걸음씩 구성할 수 있는 것만 수학의 대상으로 인정하자고 했습니다(직관주의). 예를 들어 "이런 수가 있다"고 말하려면 그 수를 실제로 만들어 보이는 방법까지 내놓아야 한다는 것입니다. 괴팅겐의 다비트 힐베르트는 수학 전체를 기호 규칙의 체계로 적은 다음, 그 체계에 모순이 없음을 유한한 방법으로 증명하자고 했습니다(형식주의). '유한한 방법'이란 무한한 집합 전체를 한꺼번에 다루지 않고, 유한한 기호열을 규칙대로 하나씩 살피는 것만으로 확인할 수 있는 추론을 말합니다. 두 사람의 다툼은 「무한에도 크기가 있다」 7절에 있습니다.

이 글의 질문과 이어지는 쪽은 힐베르트입니다. 여기서 '체계'란 증명 없이 받아들이는 출발점 명제인 공리⁠(axiom)⁠들과, 이미 얻은 식에서 새 식을 끌어내는 추론 규칙을 정해 둔 것이고, '증명'이란 공리에서 시작해 규칙만으로 한 줄씩 이어 간 식의 나열입니다. 예를 들어 공리 "모든 수 x에 대해 x + 0 = x"와 "'모든 x에 대해 ~'에서 x 자리에 아무 수나 넣어도 된다"는 규칙이 있으면, 한 줄 만에 "3 + 0 = 3"이 증명됩니다.

그의 계획에는 목표가 셋 있었습니다. 첫째, 체계는 무모순⁠(consistent)⁠이어야 합니다. 어떤 명제와 그 부정을 둘 다 증명하는 일이 없어야 한다는 뜻입니다. 둘째, 참인 명제는 모두 증명할 수 있어야 합니다(완전성). 셋째, 어떤 명제가 증명되는지 가려내는 기계적인 절차가 있어야 합니다(결정 가능성⁠, decidability⁠).

'기계적인 절차'란 두 수의 최대공약수⁠(greatest common divisor)⁠를 구하는 유클리드 호제법⁠(Euclidean algorithm)⁠처럼, 생각 없이 정해진 규칙만 따라가도 유한한 걸음 안에 반드시 답에 이르는 방법을 말합니다. 이런 방법을 알고리즘⁠(algorithm)⁠이라고 부릅니다. 예를 들어 12와 8이면, 12를 8로 나눈 나머지⁠(remainder)⁠ 4를 구하고, 다시 8을 4로 나누면 나머지가 0이니 최대공약수는 4입니다. 어떤 두 자연수를 넣어도 나눗셈을 몇 번 되풀이하면 반드시 끝납니다.

세 번째 목표에 이름이 붙은 것은 1928년입니다. 힐베르트와 제자 빌헬름 아커만은 교과서 『이론 논리학의 기초』에서 이것을 '결정 문제'(독일어로 Entscheidungsproblem)라 부르며, 수학의 방법으로 논리와 증명 자체를 연구하는 분야인 수리 논리학⁠(mathematical logic)⁠의 주된 문제라고 했습니다.

두 사람은 이 목표를 논리의 말로 다듬었습니다. 산술이든 기하든 공리를 유한 개 골라 적으면, '이 공리들에서 명제 P가 증명되는가'는 '(공리 1 그리고 공리 2 그리고 …)이면 P이다'라는 논리식 하나가 공리 없이 논리 법칙만으로 증명되는가라는 물음이 됩니다. 그래서 결정 문제⁠(decision problem)⁠는 정확히는 이렇게 묻습니다. '모든'과 '어떤'이 들어간 논리식(1차 논리식이라고 부릅니다)이 주어지면, 그 식이 논리 법칙만으로 증명되는지를 기계적으로 가려낼 수 있는가? 아래 곁글의 완전성 정리⁠(completeness theorem)⁠에 따르면 이것은 '그 식이 기호를 어떻게 해석하든 언제나 참인가'를 묻는 것과 같습니다.

1928년 9월에는 대략 4년마다 세계의 수학자들이 모이는 국제수학자대회가 볼로냐에서 열렸고, 힐베르트는 그 자리에서 이 질문들을 다시 내놓았습니다. 이번 대회는 1차 세계대전 뒤 독일 수학자들이 처음으로 초대받은 국제수학자대회였고, 독일 안에서는 참가를 거부하자는 목소리도 있었습니다. 힐베르트는 70명 가까운 독일 대표단을 이끌고 참석했습니다. 수학에는 국경이 없다는 것이 그의 입장이었습니다.

그해 12월에는 케임브리지의 프랭크 램지가 런던 수학회에서 결정 문제의 한 특수한 경우를 푼 논문을 읽었습니다. 모든 논리식이 아니라 특정한 모양의 논리식에 한해서는, 그 식이 언제나 참인지를 기계적으로 가려내는 절차가 있음을 보인 것입니다. 그 증명의 한 단계로 쓴 작은 정리(보조정리⁠, lemma⁠)가 뒤에 램지 이론⁠(Ramsey theory)⁠이라는 조합론⁠(combinatorics)⁠의 한 분야로 자랐습니다(「완전한 무질서는 없다」 3절).

힐베르트와 아커만의 책에는 풀리지 않은 문제가 하나 더 적혀 있었습니다. 논리의 규칙만으로, 기호가 무엇을 가리키든 늘 참인 논리식을 모두 증명할 수 있는가? 빈 대학의 대학원생이던 괴델이 1929년 박사 논문에서 '그렇다'고 답했습니다(완전성 정리). 이름이 비슷해 헷갈리기 쉽지만, 2년 뒤의 불완전성 정리⁠(incompleteness theorem)⁠와 부딪치지 않습니다. 완전성 정리의 '참'은 기호를 어떻게 해석하든 참이라는 뜻이고, 불완전성 정리의 '참'은 실제 자연수 0, 1, 2, …라는 한 가지 해석에서 참이라는 뜻입니다. 한편 '그리고', '또는', '아니다'만 쓰는 명제 논리⁠(propositional logic)⁠에서는 결정 문제가 이미 풀려 있었습니다. 1절의 진리표처럼 변수에 0과 1을 넣는 경우를 모두 따져 보면 되기 때문입니다. 뉴욕의 에밀 포스트가 1920년 컬럼비아 대학 박사 논문을 바탕으로 1921년에 낸 논문에서 이것을 보였습니다. 어려운 것은 '모든'과 '어떤'이 들어간 논리였습니다. 변수가 끝없이 많은 대상을 가리킬 수 있어서, 경우를 모두 따져 보는 방법이 통하지 않기 때문입니다.

'알고리즘'이라는 낱말은 9세기 바그다드의 학자 알콰리즈미의 이름에서 왔습니다. 인도에서 온 숫자로 셈하는 법을 적은 그의 책은 12세기에 '알고리즈미가 말하기를'(Dixit Algorizmi)로 시작하는 라틴어로 옮겨졌고, 중세 유럽에서는 이 셈법 자체를 그의 이름을 따 알고리스무스라고 불렀습니다. 종이 위에서 손으로 따라 하는 셈의 절차를 가리키던 말이, 기계가 할 수 있는 일을 가리키는 말이 된 것입니다.

힐베르트는 풀 수 없는 수학 문제는 없다고 믿었습니다. 1872년 베를린의 생리학자 에밀 뒤부아레몽은 라이프치히에서 열린 독일 자연과학자·의사 대회에서, 물질의 궁극적인 본성과 의식의 수수께끼 앞에서 과학은 "우리는 모르고, 앞으로도 모를 것이다(ignoramus et ignorabimus)"라고 말할 수밖에 없다고 연설했습니다. 힐베르트는 1900년 파리 연설에서 이미 수학에는 그런 '모를 것이다'가 없다고 맞받았습니다. 1930년 같은 대회가 그의 고향 쾨니히스베르크에서 열리자, 그해 은퇴한 힐베르트는 이 오래된 논쟁을 다시 꺼냈습니다. 라디오로도 방송된 그 연설의 마지막 문장 "우리는 알아야 한다. 우리는 알게 될 것이다"는 지금 괴팅겐에 있는 그의 묘비에 새겨져 있습니다. 그런데 바로 그 전날, 같은 도시의 한 학회에서 빈의 쿠르트 괴델이 반대 방향의 결과를 짧게 알렸습니다(「무한에도 크기가 있다」 7절). 여기서는 그 증명의 핵심 기술을 직접 해 봅니다.

라이프니츠에서 튜링까지의 연표와 지도입니다. 코크, 예나, 케임브리지, 괴팅겐, 빈, 쾨니히스베르크처럼 논리학의 무대가 된 도시들이 대부분 대학 도시라는 것을 보세요. 지도의 선은 편지와 여행입니다. 점이나 지명에 마우스를 올리면 그곳에서 일어난 일이 나옵니다.

괴델의 첫 번째 착상은 기호마다 번호를 붙이고, 기호가 늘어선 식을 하나의 자연수로 바꾸는 것이었습니다. 식 하나로 해 봅시다. 기호 0에 1번, = 에 3번을 붙였다면, 식 「0 = 0」의 기호 번호는 차례로 1, 3, 1입니다. 첫째 소수⁠(prime number)⁠ 2를 1번, 둘째 소수 3을 3번, 셋째 소수 5를 1번 곱하면 $2^1 \cdot 3^3 \cdot 5^1 = 2 \cdot 27 \cdot 5 = 270$입니다. 이 270이 식 「0 = 0」의 번호, 곧 괴델 수입니다.

일반적으로 적으면, $k$번째 기호의 번호가 $c_k$이면 $k$번째 소수를 $c_k$번 곱합니다. 아래 그림에서 식을 고르거나 기호 단추를 눌러 식을 만들면, 각 기호가 소수의 거듭제곱으로 바뀌고 그것들을 모두 곱한 수가 나옵니다. 식 의 기호들을 소수의 거듭제곱으로 바꾸어 곱하면

이 식의 괴델 수⁠(Gödel number)⁠는 입니다. 아래 단추로 기호를 하나씩 덧붙여 자기만의 식을 만들 수도 있습니다. 식 지우기

거꾸로도 됩니다. 1보다 큰 자연수를 소수의 곱으로 쓰는 방법은 곱하는 순서를 빼면 오직 한 가지뿐이므로(산술의 기본정리⁠(fundamental theorem of arithmetic)⁠, 소인수분해⁠(prime factorization)⁠), 수 하나에서 식을 되찾을 수 있습니다. 2의 지수가 첫 기호, 3의 지수가 둘째 기호의 번호입니다. 270 = 2¹ · 3³ · 5¹이면 지수가 1, 3, 1이니 「0 = 0」입니다. 수를 끌어 바꿔 보세요: . 1,350을 넣으면 「0 = S」가 나옵니다. 기호열이긴 하지만 문법에 맞는 식은 아닙니다.

이 번호 매기기 덕분에 식에 관한 이야기가 수에 관한 이야기가 됩니다. 예를 들어 '번호가 n인 식은 = 기호로 시작한다'는 말은 'n은 $2^3$으로 나누어떨어지지만 $2^4$으로는 나누어떨어지지 않는다'는 수의 성질과 같습니다. 같은 식으로, 어떤 수가 올바른 식의 번호인지, 어떤 수가 어떤 식의 증명(식들의 나열)의 번호인지도 모두 나눗셈과 곱셈으로 따질 수 있는 수의 성질이 됩니다.

여기서 괴델의 두 번째 착상이 나옵니다. 식은 수로 바뀌므로, 산술의 식이 다른 식의 번호에 대해, 나아가 자기 자신의 번호에 대해 말할 수 있습니다. 괴델은 "번호가 $n$인 식을 증명하는 증명은 없다"처럼 빈자리 $n$이 있는 식을 만들고, 그 빈자리에 식 자신의 번호가 들어가도록 짜 맞추는 기술을 썼습니다(오늘날 대각선 보조정리라 부르며, 자기 참조⁠(self-reference)⁠의 대표적인 예입니다). 그렇게 해서 다음과 같은 뜻을 담은 산술의 식 $G$를 만들었습니다.

$\ulcorner G \urcorner$('G의 번호')는 $G$ 자신의 괴델 수이고, ⟺는 양쪽이 같은 말이라는 뜻입니다. 그러니 $G$는 "나는 증명할 수 없다"고 말하는 문장입니다.

이 문장이 증명되는지 두 단계로 따져 봅시다.

첫째, $G$가 증명된다고 해 봅시다. 그 증명은 실제로 있는 유한한 기호열이고, 그것이 증명인지 확인하는 일은 계산이므로 체계 안에서도 따라 할 수 있습니다. 그러면 체계는 '$G$는 증명할 수 있다'도 증명하는데, 이것은 $G$의 부정과 같은 말입니다($G$가 '나는 증명할 수 없다'였으니까요). 체계가 한 문장과 그 부정을 함께 증명하게 되니 모순입니다.

둘째, 그러니 체계에 모순이 없다면 $G$는 증명되지 않습니다. 그런데 $G$가 말하는 내용이 바로 '$G$는 증명되지 않는다'이니, $G$는 참입니다. 참이지만 증명할 수 없는 문장입니다. 여기서 '참'은 실제 자연수 0, 1, 2, …에 대해 성립한다는 뜻이고, '증명할 수 없다'는 이 체계의 공리와 규칙으로는 끌어낼 수 없다는 뜻입니다.

이 논증은 특정한 체계 하나가 아니라 세 조건을 갖춘 모든 형식 체계⁠(formal system)⁠에 통합니다. 첫째, 공리의 목록을 기계가 하나씩 차례로 적어 낼 수 있어야 합니다(공리가 유한 개이거나, 규칙에 따라 만들어져야 합니다). 둘째, 자연수의 덧셈과 곱셈에 관한 기본 사실을 표현하고 증명할 수 있어야 합니다. 셋째, 모순이 없어야 합니다. 1889년 주세페 페아노가 정리한 자연수의 공리 체계인 페아노 산술⁠(Peano arithmetic)⁠이 대표적인 예입니다. 이런 체계에는 반드시 참이지만 증명할 수 없는 문장이 있습니다. 이것이 1931년 빈에서 발표된 제1 불완전성 정리입니다.

흔히 이 정리를 '수학에는 영원히 증명할 수 없는 참이 있다'로 줄여 말하지만, 정리가 말하는 것은 주어진 체계 하나에 대해서입니다. $G$를 새 공리로 덧붙이면 $G$는 물론 증명됩니다. 그러나 덧붙여 커진 체계도 세 조건을 갖추는 한, 같은 방법으로 그 체계의 새 괴델 문장이 생깁니다. 구멍은 메울 수 있지만, 구멍이 없는 체계는 만들 수 없습니다.

괴델은 한 걸음 더 나아갔습니다. 체계가 자기 자신에 모순이 없다는 것을 스스로 증명할 수 있을까요? 힐베르트의 계획이 바란 것이 바로 이런 증명이었습니다. 괴델의 답은 "이 체계에는 모순이 없다"는 문장 자체가 그런 구멍의 하나라는 것, 곧 체계가 자기의 무모순성⁠(consistency)⁠을 증명할 수 없다는 것입니다(제2 정리). 왜 그런지 세 걸음으로 따라가 봅시다.

첫 걸음은 "이 체계에는 모순이 없다"를 산술의 식으로 적는 것입니다. 모순이 있는 체계는 무엇이든 증명합니다. 한 문장과 그 부정을 둘 다 증명하면, 거기서 어떤 문장이든 끌어낼 수 있기 때문입니다. 그러니 뻔한 거짓인 「0 = S0」(0 = 1)을 증명하는지만 보면 됩니다. 무모순성은 "번호가 $\ulcorner 0 = S0 \urcorner$인 식을 증명하는 증명은 없다"라는 수의 성질로 적힙니다. 이 식을 Con이라 부릅시다(무모순성, consistency의 줄임).

둘째 걸음은 앞의 둘째 단계를 다시 보는 것입니다. 거기서 우리는 "체계에 모순이 없다면 $G$는 증명되지 않는다"를 보였습니다. $G$가 말하는 것이 바로 '$G$는 증명되지 않는다'이니, 이것은 "Con이면 $G$"입니다. 괴델이 짚은 요점은, 이 추론이 증명과 괴델 수에 관한 수의 계산일 뿐이라서 체계 안에서도 그대로 따라 할 수 있다는 것입니다. 곧 체계는 "Con이면 $G$"를 증명합니다.

셋째 걸음에서 결론이 나옵니다. 체계가 Con까지 증명한다고 해 봅시다. 그러면 "Con이면 $G$"와 "Con"에서 $G$도 증명됩니다("$A$이면 $B$"와 "$A$"에서 "$B$"를 끌어내는 규칙입니다). 하지만 앞의 두 단계에서 본 대로, 모순이 없는 체계는 $G$를 증명하지 못합니다. 그러니 모순이 없는 체계는 Con을 증명하지 못합니다. 앞의 세 조건을 갖춘 모든 체계에 대해 그렇습니다. 이것이 제2 불완전성 정리입니다.

흔히 이 정리를 '산술에 모순이 있을지도 모른다'는 뜻으로 읽지만, 정리가 말하는 것은 증명에 쓰는 도구에 관한 것입니다. 한 체계의 무모순성은 그보다 강한 체계에서는 증명될 수 있습니다. 아래의 겐첸이 그 예입니다. 거꾸로 생각해 보면 이 정리가 덜 이상하게 보입니다. 모순이 있는 체계는 무엇이든 증명하니, 자기의 무모순성도 '증명'합니다. 그러니 체계가 스스로 무모순성을 증명했다는 사실만으로는 처음부터 아무것도 보장되지 않았을 것입니다.

쾨니히스베르크에서 첫 발표를 들은 존 폰 노이만은 1930년 11월 스스로 제2 정리에 이르러 괴델에게 편지를 보냈지만, 괴델은 이미 그것을 논문에 넣은 뒤였습니다.

힐베르트가 바란 방식, 곧 유한한 방법으로 수학 전체의 무모순성을 증명한다는 계획은 여기서 막혔습니다. 괴팅겐에서 힐베르트의 조수를 지낸 논리학자 게르하르트 겐첸이 1936년 산술의 무모순성을 증명했지만, 그러려면 보통의 수학적 귀납법보다 더 멀리 나아가는 귀납 원리 하나를 옳다고 가정해야 했습니다. 이 가정은 페아노 산술 안에서는 증명되지 않으니, 겐첸의 증명은 제2 정리와 부딪치지 않습니다. 산술보다 강한 도구로 산술의 무모순성을 증명한 것입니다.

논문은 1930년 11월 17일 빈의 학술지 『수학·물리학 월보』에 접수되어 1931년에 실렸습니다. 괴델은 스물네 살이었습니다. 제목은 「『수학 원리』 및 관련 체계의 형식적으로 결정 불가능한 명제에 대하여 I」입니다. 2절에서 본 러셀과 화이트헤드의 체계를 대표로 겨냥했고, 논증이 그 체계 하나에 매이지 않는다는 것을 '관련 체계'라는 말로 밝혔습니다. 제목 끝의 'I'은 제2 정리의 자세한 증명을 담을 속편을 예고한 것이었지만, 속편은 끝내 나오지 않았습니다. 괴델은 이 논문을 1932년 빈 대학에 교수 자격 논문으로 냈습니다. 그 무렵의 빈은 철학의 무대이기도 했습니다. 괴델은 스승인 수학자 한스 한을 따라, 철학자 모리츠 슐리크를 중심으로 모인 빈 학파의 토론에 드나들었습니다. 빈 학파는 과학의 언어를 논리로 정리하면 관찰로 확인할 수 없는 형이상학(눈에 보이는 세계 너머의 궁극적인 것을 따지는 철학)을 걷어 낼 수 있다고 믿었지만, 괴델 자신은 8절에서 보듯 수학의 대상이 사람과 독립적으로 있다고 믿는 쪽이었습니다. 1936년 슐리크가 대학에서 옛 학생의 총에 숨지고 1938년 오스트리아가 독일에 병합되면서 빈의 학자들은 흩어졌습니다. 괴델은 1940년 초 시베리아 횡단 철도와 일본을 거쳐 미국으로 건너가 프린스턴 고등연구소에 자리 잡았습니다.

그렇다면 결정 문제는 어떻게 되었을까요? 불완전성 정리는 모든 참을 증명할 수는 없다고 말할 뿐, 어떤 식이 증명되는지를 기계로 가려낼 수 없다고 말하지는 않습니다. "기계로 가려낼 수 없다"고 말하려면 먼저 '기계로 할 수 있는 일' 전체를 정확히 정의해야 했습니다. 모든 가능한 방법을 한꺼번에 물리쳐야 하니까요.

4 · 종이 앞의 사람튜링 기계⁠(Turing machine)⁠

이 절의 물음은 이것입니다. "기계로 가려낼 수 있다"는 말을 정확히 하려면, '기계적인 절차'가 할 수 있는 일 전체를 어떻게 적어야 할까?

1935년 봄 케임브리지의 수학자 맥스 뉴먼은 수학 기초론 강의에서 힐베르트의 결정 문제를 소개하며 '기계적인 절차'라는 말을 썼습니다. 킹스 칼리지의 젊은 펠로(칼리지에 소속된 연구원) 앨런 튜링은 이 말을 문자 그대로 받아들였습니다. 그의 출발점은 기계가 아니라 사람이었습니다. 당시 영어에서 'computer'는 계산을 직업으로 하는 사람을 뜻했습니다. 종이 위에서 계산하는 사람이 하는 일을 끝까지 쪼개면 무엇이 남을까요?

• 종이는 칸으로 나눠진 긴 띠로 바꿔도 됩니다. 각 칸에는 유한한 종류의 기호 하나가 들어갑니다.
• 사람은 한 번에 몇 칸만 봅니다. 한 번에 한 칸만 본다고 해도 잃는 것이 없습니다.
• 사람의 '마음 상태'는 유한한 가짓수뿐입니다. 지금 무엇을 하는 중인지 기억하는 정도입니다.
• 한 걸음에는 한 가지만 합니다. 지금 칸의 기호를 고쳐 쓰고, 한 칸 옮기고, 마음 상태를 바꿉니다. 무엇을 할지는 지금 상태와 지금 읽은 기호만으로 정해집니다.

남는 것은 테이프, 그 위를 오가는 머리, 그리고 규칙표뿐입니다. 이것이 튜링 기계입니다. 규칙표의 한 칸은 "상태가 R이고 1을 읽었으면, 1을 그대로 쓰고 오른쪽으로 한 칸 가고 상태 R을 유지한다"처럼 한 걸음에 할 일을 적습니다. 기계는 매 걸음 지금 상태와 지금 칸의 기호에 맞는 칸 하나를 찾아 그대로 할 뿐입니다.

기계를 로 골라 돌려 보세요. 입력 수는 입니다. 그림 아래의 ▶|(다음 단계) 단추를 누르면 한 걸음씩, ▶를 누르면 저절로 나아갑니다. 매 걸음 노란 테두리의 규칙 하나만 쓰인다는 것을 눈여겨보세요.

지금 상태는 입니다.

'2진수에 1 더하기'를 입력 11로 따라가 봅시다. 11은 이진법으로 1011입니다. 상태 R의 머리는 1, 0, 1, 1을 그대로 두고 오른쪽 끝의 빈칸까지 간 뒤, 상태 C로 바꾸고 왼쪽으로 한 칸 돌아옵니다. 상태 C에서 1을 읽으면 0으로 고치고 왼쪽으로 가니(올림), 끝의 두 1이 차례로 0이 됩니다. 그다음 0을 읽으면 1로 고치고 멈춥니다. 테이프에는 1100, 곧 12가 남습니다. 손으로 하는 받아올림과 똑같습니다.

튜링 기계는 보잘것없어 보이지만, 튜링은 사람이 종이와 연필로 할 수 있는 어떤 계산도 이런 기계로 흉내 낼 수 있다고 논증했습니다. 앞의 목록이 그 논증의 뼈대입니다. 계산하는 사람이 하는 일을 쪼개면 결국 '한 칸 읽고, 고쳐 쓰고, 옮기고, 마음 상태를 바꾸기'만 남기 때문입니다.

더 중요한 발견은 따로 있었습니다. 규칙표도 기호의 나열이니 테이프에 적을 수 있습니다. 그러면 테이프에서 다른 기계의 규칙표를 읽고 그 기계가 할 일을 한 걸음씩 대신하는 기계를 하나 만들 수 있습니다. 튜링은 이것을 보편 기계⁠(universal machine)⁠라고 불렀습니다. 기계마다 따로 배선하지 않고, 기계 하나에 프로그램을 바꿔 넣는다는 생각입니다. 여러분이 지금 보는 화면의 컴퓨터가 바로 그런 기계입니다(기억 장치가 유한하다는 점만 빼면). 정리하면, 튜링 기계 하나하나는 프로그램 하나이고, 보편 기계는 그 프로그램을 읽어 돌리는 컴퓨터입니다.

같은 무렵 대서양 건너편에서도 같은 질문에 답이 나오고 있었습니다. 프린스턴의 논리학자 알론조 처치는 함수⁠(function)⁠를 만들고 적용하는 규칙만으로 계산을 적는 람다 계산⁠(lambda calculus)⁠을 세웠고, 1936년 봄 이를 이용해 결정 문제에 튜링보다 조금 먼저 부정의 답을 냈습니다. 뉴욕 시티 칼리지의 수학자 에밀 포스트도 같은 해에 '일꾼' 모형을 발표했습니다. 일꾼이 상자들 사이를 오가며 표시를 하는 모형으로, 튜링 기계와 거의 같습니다. 처치의 람다 계산이 뒤에 타입⁠(type)⁠을 얻어 증명의 언어가 되는 이야기는 「증명은 프로그램이다」 3절에 있습니다.

세 정의는 겉모습이 전혀 달랐지만 결국 같은 것이었습니다. 튜링은 논문에 부록을 붙여 자기 기계로 계산할 수 있는 것과 람다 계산으로 정의할 수 있는 것이 정확히 같다는 증명의 줄기를 적었고, 이듬해 자세한 증명을 따로 발표했습니다. 서로 전혀 다른 정의들이 같은 곳에 이르자, 수학자들은 이것이 '기계적으로 계산할 수 있음'의 올바른 정의라고 받아들이게 됩니다. 이 주장을 처치–튜링 논제⁠(Church–Turing thesis)⁠라고 합니다. '계산할 수 있다'는 직관적 개념과 수학적 정의가 같다는 주장이어서 증명할 수 있는 정리가 아니라 논제입니다. 처치 쪽 정의에 회의적이던 괴델도 튜링의 분석은 설득력 있다고 여겼습니다.

튜링은 처치의 결과를 모른 채 일했습니다. 원고가 런던 수학회에 접수된 것은 1936년 5월 28일인데, 바로 그 무렵 처치의 논문이 케임브리지에 도착했습니다. 한발 늦은 셈이었지만 뉴먼은 두 접근이 전혀 다르다고 보아 논문을 그대로 싣게 했고, 5월 31일 처치에게 편지를 보내 튜링이 프린스턴에서 배울 수 있게 해 달라고 부탁했습니다. 논문은 그해 11월 학회에서 읽히고 연말에 두 번에 나뉘어 실렸습니다. 처치는 1937년 『기호 논리학 저널』에 쓴 서평에서 이 기계를 처음 '튜링 기계'라고 불렀습니다.

포스트는 누구보다 먼저 이 길에 들어선 사람이었습니다. 뒤에 그가 적은 바에 따르면, 1920년대 초 기호를 바꿔 쓰는 규칙의 체계를 연구하던 그는 모든 체계를 흉내 내는 체계가 있고, 그래서 판정할 수 없는 문제와 증명할 수 없는 명제가 있으리라는 결론에 이르렀습니다. 하지만 자기의 정의가 정말 모든 기계적 절차를 담는지 더 따져 봐야 한다고 여겨 발표하지 않았습니다. 조울증으로 여러 번 입원하며 연구가 자주 끊기기도 했습니다. 이 사정을 적어 1941년 학술지에 보낸 글은 실리지 못했고, 그가 세상을 떠나고 11년 뒤인 1965년에야 논리학자 마틴 데이비스가 엮은 『결정 불가능한 것』에 실렸습니다.

1936년 가을 튜링은 프린스턴으로 건너가 처치 밑에서 박사 학위를 받았습니다. 프린스턴 고등연구소의 폰 노이만이 조수 자리를 제안했지만 튜링은 거절하고 1938년 여름 영국으로 돌아왔습니다. 박사 논문 「순서수⁠(ordinal number)⁠에 기초한 논리 체계」(1938)가 물은 것은 이것입니다. 괴델 문장처럼 증명되지 않는 참을 새 공리로 덧붙이는 일을 3절의 초한 순서를 따라 끝없이 되풀이하면 어디까지 갈 수 있는가? 그 논문에서 튜링은 '신탁'을 단 기계도 생각했습니다. 정지 문제⁠(halting problem)⁠처럼 기계가 풀 수 없는 물음에 한 번에 답해 주는 상자를 붙인 튜링 기계입니다. 그런 기계도 자기와 같은 종류의 기계가 멈추는지는 판정하지 못한다는 것이 같은 대각선 논법으로 나오니, 풀 수 없는 문제에도 층이 있습니다. 5절에서 쌍둥이 소수 추측⁠(twin prime conjecture)⁠이 정지 판정기에 한 번 묻는 것으로는 풀리지 않는다고 할 때의 '한 단계 더'가 이 층입니다.

5 · 멈출지 아는 기계는 없다정지 문제

이 절의 물음은 이것입니다. 프로그램과 입력을 받아, 그 프로그램이 언젠가 멈출지 영원히 돌지를 늘 옳게 알려 주는 프로그램을 만들 수 있을까? 답은 "없다"이고, 이것이 결정 문제의 답으로 이어집니다.

앞 그림의 '끝없이 세기'를 250걸음 돌려 보았다면, 그 기계가 영원히 멈추지 않는다는 것을 우리는 압니다. 규칙표에 멈춤이 없으니까요. 하지만 대부분의 기계는 그렇게 쉽게 들여다보이지 않습니다. 오래 도는 기계가 곧 멈출지, 영원히 돌지는 지켜보는 것만으로는 알 수 없습니다.

'바쁜 비버'가 그 어려움을 보여 줍니다. 규칙을 먼저 정해 둡시다. 기계는 빈 테이프에서 시작하고, 테이프에는 빈칸과 1 두 가지 기호만 씁니다. 상태 수가 같은 기계들 가운데 언젠가 멈추는 것만 겨루는데, 재는 방법이 둘입니다. 멈췄을 때 테이프에 남은 1의 개수, 그리고 멈출 때까지의 걸음 수입니다. 4절 그림의 '바쁜 비버' 기계는 14걸음 만에 멈추며 1을 6개 남깁니다. 상태가 3개인 멈추는 기계는 1을 많아야 6개 쓰니, 그 기계가 1의 개수로는 1등입니다. 걸음 수로 재면 상태 3개의 최댓값은 21걸음이어서, 1을 가장 많이 쓰는 기계와 가장 오래 도는 기계가 꼭 같지는 않습니다.

상태 수를 늘리면 최댓값이 이렇게 자랍니다. 상태가 4개이면 1은 많아야 13개, 걸음은 많아야 107걸음입니다. 상태가 5개가 되면 1은 4,098개, 가장 오래 도는 기계는 47,176,870걸음 만에 멈춥니다. 상태를 한두 개 늘렸을 뿐인데 걸음 수가 수천만으로 뛰었습니다. 그런데 어려움은 크기만이 아닙니다. 5개짜리 기계 하나를 1억 걸음 돌려도 멈추지 않았다면, 그 기계가 영원히 도는지 1억 1걸음째에 멈출지는 지켜보는 것만으로는 알 수 없습니다.

47,176,870걸음짜리 기계는 1990년 하이너 마르크센과 위르겐 분트로크가 찾아 두었지만, 이 값이 정말 최대라는 것은 2024년 7월에야 확인되었습니다. 최대임을 보이려면 상태 5개짜리 다른 모든 기계가 그보다 먼저 멈추거나 영원히 돈다는 것을 하나하나 증명해야 합니다. 2022년에 시작된 온라인 공동 연구 모임 bbchallenge가 엄청나게 많은 기계를 하나하나 멈추는지 따졌고, 끝까지 버틴 몇몇 기계는 저마다 따로 증명해야 했습니다. 이 기계들을 처음 정의한 사람은 헝가리 출신의 미국 수학자로 오하이오 주립 대학에 있던 티보르 라도입니다.

라도는 1962년 벨 연구소의 학술지 『벨 시스템 기술 저널』에 실은 논문 「계산할 수 없는 함수에 대하여」에서 더 깊은 사실을 보였습니다. '상태가 n개인 멈추는 기계가 걸을 수 있는 최대 걸음 수'를 n의 함수로 보면, 이 함수는 계산 가능한 함수가 아닙니다. 계산 가능한 함수란 입력 n을 받아 값을 적고 멈추는 튜링 기계가 있는 함수를 말합니다. 라도의 함수는 그런 함수를 어느 것을 골라도, n이 충분히 커지면 그 함수보다 더 커집니다. 곧 이 값을 계산해 주는 기계는 있을 수 없습니다. 왜 그런지는 아래에서 정지 문제를 증명한 뒤 짧게 보입니다.

그렇다면 아무 프로그램과 입력을 받아 그 프로그램이 멈출지를 늘 옳게 답하는 프로그램 $H$가 있을 수 있을까요? 증명은 대각선 논법으로 합니다. 먼저 $H$가 있다고 가정하고, 거기서 모순을 끌어내겠습니다.

프로그램은 유한한 글자로 적히므로 가산 개, 곧 자연수처럼 1번, 2번, …으로 번호를 매길 수 있을 만큼 있습니다. 짧은 것부터, 길이가 같으면 사전 순으로 늘어놓으면 됩니다. 1번 프로그램을 $P_1$('피 일'), 2번을 $P_2$, 이렇게 부릅니다. 아래 표의 $k$번째 줄은 $k$번 프로그램 $P_k$가 입력 $n$에서 멈추는지(멈춤) 영원히 도는지(∞)를 적은 것입니다. 1번은 무조건 멈추고, 2번은 무조건 돌고, 3번은 짝수가 들어오면 멈추는 식입니다. 예를 들어 3번째 줄 4번째 칸은 '$P_3$에 4를 넣으면 멈춘다'입니다. $H$가 있다면 이 표의 어느 칸이든 계산할 수 있습니다.

그림에서 볼 것은 노란 테두리의 대각선($k$번째 줄의 $k$번째 칸)과 맨 아래 D의 줄입니다. D의 줄이 대각선을 한 칸씩 뒤집은 것이라는 것, 그래서 위의 어느 줄과도 같지 않다는 것을 확인해 보세요.

이제 프로그램 $D$를 만듭니다. $D$는 입력 $n$을 받으면 $H$에게 "$P_n$에 $n$을 넣으면 멈추는가?"를 묻고, 답의 반대로 합니다. 멈춘다고 하면 영원히 돌고, 돈다고 하면 곧바로 멈춥니다. 예를 들어 $P_1$은 1을 넣으면 멈추므로 $D$는 1을 받으면 영원히 돌고, $P_2$는 2를 넣으면 돌므로 $D$는 2를 받으면 멈춥니다. 그러면 $D$의 줄은 대각선을 뒤집은 것이 됩니다. $H$가 있다면 $D$는 $H$를 부품으로 쓰는 평범한 프로그램이니, 목록 어딘가에 있어야 합니다. $D$가 번째 줄이라고 해 봅시다.

어느 줄을 골라도 $k$번째 칸에서 어긋납니다. 칸을 눌러 표를 아무렇게나 바꿔도 마찬가지입니다. 표 되돌리기 목록 전체를 한 번에 보지 않고 $D$의 번호를 $d$라 불러 곧바로 물어도 됩니다. $D$에 자기 번호 $d$를 넣으면 고 가정합시다. 어느 가정도 성립하지 않으니 처음의 가정, 다시 말해 $H$가 있다는 가정이 틀렸습니다. 모든 프로그램에 대해 멈춤 여부를 옳게 판정하는 프로그램은 없습니다. 이것이 정지 문제입니다.

흔히 '더 똑똑하게 짜면 언젠가 만들 수 있지 않을까' 하고 생각하지만, 이 논증은 $H$가 어떻게 짜여 있는지를 전혀 쓰지 않았습니다. 어떤 $H$를 가져와도 그 $H$로 $D$를 만들면 틀리는 입력이 생깁니다. 또 이 정리는 '어떤 프로그램도 멈출지 알 수 없다'는 뜻이 아닙니다. 앞의 '끝없이 세기'처럼 특정한 프로그램의 멈춤은 얼마든지 알아낼 수 있습니다. 없는 것은 모든 프로그램에 대해 늘 옳게 답하는 하나의 방법입니다.

러셀의 $R$, 괴델의 $G$, 튜링의 $D$는 모두 자기 자신에 대해 묻고 그 답을 뒤집습니다. 차이는 결론에 있습니다. 러셀의 역설은 "성질마다 집합이 있다"고 믿던 초기의 소박한 집합론을 무너뜨렸지만, 괴델과 튜링은 같은 모양의 논증으로 체계를 무너뜨리는 대신 체계의 한계를 증명했습니다.

여기서 결정 문제의 답이 나옵니다. 기계 $M$과 입력 $n$이 주어지면, "기계 $M$이 입력 $n$에서 언젠가 멈춘다"는 사실을 논리식 하나로 적을 수 있습니다. 튜링 기계의 한 걸음은 '지금 상태, 머리의 위치, 테이프의 내용'을 규칙표에 따라 다음 것으로 바꾸는 일이라, 괴델 수를 쓰듯 수에 관한 식으로 적을 수 있습니다. 그러면 "어떤 수 t가 있어서, t걸음 뒤의 상태가 '멈춤'이다"라는 식이 됩니다.

이 식은 $M$이 실제로 멈출 때 그리고 그때에만 증명됩니다. 멈춘다면, 멈출 때까지의 걸음들을 한 줄씩 적어 확인한 것이 그대로 증명이 됩니다. 멈추지 않는다면 식이 거짓이니, 거짓을 증명하지 않는 체계에서는 증명되지 않습니다. 그러니 어떤 식이 증명되는지 가려내는 기계가 있으면, 그 식을 적어 물어보는 것으로 정지 문제도 풀립니다.

남은 고리가 하나 있습니다. 3절에서 본 대로 결정 문제가 묻는 것은 공리 없이 논리 법칙만으로 증명되는가인데, 방금은 산술의 공리를 썼습니다. 다행히 걸음을 한 줄씩 확인하는 데 필요한 산술은 덧셈과 곱셈의 기본 사실 몇 가지뿐이라, 공리가 유한 개뿐인 약한 산술로 충분합니다(로빈슨 산술이 그런 예입니다). 그 공리들을 '그리고'로 모두 이은 식을 Q라 하면, 물어볼 식은 'Q이면 M이 멈춘다'라는 논리식 하나입니다. 이 식은 M이 멈출 때 그리고 그때에만 논리 법칙만으로 증명됩니다. M이 멈추면 Q만으로 'M이 멈춘다'가 증명되니 이 식이 증명되고, M이 멈추지 않으면 실제 자연수에서 Q는 참인데 'M이 멈춘다'는 거짓이니 이 식은 언제나 참인 식이 아니어서 논리만으로는 증명되지 않습니다. 그러니 결정 문제를 푸는 기계가 있으면 정지 문제가 풀립니다. 정지 문제는 풀 수 없으니, 결정 문제를 푸는 기계도 없습니다. 정리하면, 힐베르트의 셋째 목표는 이루어질 수 없습니다.

방금 쓴 방법에는 이름이 있습니다. 문제 A의 질문 하나하나를 문제 B의 질문으로 기계적으로 바꿔 적되, 두 질문의 답이 같게 하는 것을 A를 B로 환원한다고 합니다. 여기서는 A가 정지 문제, B가 결정 문제였습니다. 환원이 있으면 B를 푸는 기계로 A도 풀리니, A를 풀 수 없다면 B도 풀 수 없습니다. 방향에 주의해야 합니다. 풀 수 없음은 A에서 B로, 곧 환원의 화살표를 따라 옮겨 갑니다. 거꾸로 B를 A로 환원했다고 해서 B가 풀 수 없다는 결론은 나오지 않습니다.

이제 5절 처음의 바쁜 비버로 돌아갈 수 있습니다. 상태가 n개인 멈추는 기계의 최대 걸음 수를 계산하는 기계가 있다고 해 봅시다. 상태가 n개인 기계 하나를 빈 테이프에서 돌리는데, 최대 걸음 수만큼 돌려도 멈추지 않았다면 영원히 돌 것이 확실합니다. 멈추는 기계라면 그 전에 멈췄어야 하니까요. 그러면 '빈 테이프에서 시작한 기계가 멈추는가'를 판정할 수 있습니다. 그런데 이 문제도 풀 수 없습니다. 기계 $M$과 입력 $n$이 주어지면 '빈 테이프에 $n$을 먼저 적은 뒤 $M$처럼 움직이는 기계'를 만들 수 있어서, 정지 문제가 이 문제로 환원되기 때문입니다. 그러니 최대 걸음 수는 계산할 수 없는 함수입니다.

튜링의 1936년 논문 「계산 가능한 수⁠(computable number)⁠에 대하여, 결정 문제에의 응용과 함께」의 논증은 사실 조금 다른 모양이었고, '정지 문제'라는 이름도 1950년대에 붙은 것으로 여겨지지만 핵심은 같습니다. 칸토어에서 튜링까지 이어진 이 같은 모양의 논증들을 1969년 윌리엄 로베어가 고정점⁠(fixed point)⁠ 정리 하나로 묶은 이야기는 「불가능의 증명」 7절과 「화살표만으로 본 수학」 7절에 있습니다.

정지 판정기가 있었다면 수학자들은 할 일이 많이 줄었을 것입니다. 골드바흐 추측⁠(Goldbach's conjecture)⁠은 "4 이상의 짝수는 모두 두 소수의 합이다"라는 추측입니다(4 = 2 + 2, 10 = 3 + 7, 100 = 3 + 97). 1742년 프로이센의 수학자 크리스티안 골드바흐가 오일러에게 보낸 편지에서 비롯되었습니다. 이제 "4부터 짝수를 차례로 보며 두 소수의 합으로 쓸 수 없는 것을 찾으면 멈춘다"는 프로그램을 생각합시다. 이 프로그램이 영원히 돈다면 추측이 참이고, 멈춘다면 반례가 나온 것입니다. 그러니 이 프로그램이 멈추는지 물으면 골드바흐 추측이 풀립니다. 골드바흐 추측을 정지 문제로 환원한 것입니다. 앞에서 말한 방향을 떠올리면, 이것은 골드바흐 추측이 풀 수 없는 문제라는 뜻이 아닙니다. 정지 문제를 풀 수 있다면 골드바흐 추측도 풀린다는 뜻일 뿐입니다.

차이가 2인 소수 쌍(3과 5, 11과 13처럼)이 끝없이 있는지를 묻는 쌍둥이 소수⁠(twin primes)⁠ 추측은 한 단계 더 복잡합니다. 'N보다 큰 쌍둥이 소수를 찾으면 멈춘다'는 프로그램이 모든 N에 대해 멈추는지를 물어야 하므로, 정지 판정기에 한 번 묻는 것으로는 풀리지 않습니다. 정지 문제가 풀리지 않는다는 것은 이런 질문들을 한꺼번에 처리하는 기계적인 방법이 없다는 뜻입니다.

같은 논리가 힐베르트의 오래된 숙제 하나도 풀었습니다. 1900년 파리의 국제수학자대회에서 힐베르트는 새 세기의 수학이 풀어야 할 문제 23개를 내놓았는데, 그 10번은 다음과 같았습니다. 정수⁠(integer)⁠ 계수 다항식⁠(polynomial)⁠으로 된 방정식이 주어지면, 그 방정식에 정수해가 있는지를 유한한 걸음 안에 판정하는 방법을 찾아라. 이런 방정식을 디오판토스 방정식⁠(Diophantine equation)⁠이라 합니다. 예를 들어 $x^2 + y^2 = 3$은 정수해가 없고(제곱수⁠(perfect square)⁠ 0, 1, 4, …를 두 개 더해 3을 만들 수 없습니다), $x^2 - 2y^2 = 1$은 $x = 3, y = 2$ 같은 정수해가 있습니다(9 − 8 = 1). 미국의 논리학자 마틴 데이비스, 철학자이자 논리학자 힐러리 퍼트넘, 수학자 줄리아 로빈슨이 20년 가까이 이 문제를 두고 연구를 쌓았습니다. 1970년 레닌그라드의 스물두 살 수학자 유리 마티야세비치가 그 연구를 마무리해, 그런 판정 알고리즘은 없다는 것을 보였습니다. 10번 문제의 답이 '불가능'이었던 것입니다.

증명의 뼈대는 이번에도 환원입니다. 어떤 기계와 입력이 주어지든, "이 기계가 이 입력에서 멈춘다"와 "이 방정식에 정수해가 있다"가 같은 말이 되는 디오판토스 방정식을 기계적으로 만들 수 있다는 것입니다. 그러면 정수해를 판정하는 방법이 곧 정지 문제를 푸는 방법이 되니, 그런 방법은 있을 수 없습니다. 정지 문제에서 결정 문제로 옮겨 간 '풀 수 없음'이, 이번에는 방정식으로 옮겨 간 것입니다.

이 풀이는 냉전의 양쪽에서 이어 쌓은 것입니다. 1950년대 초 버클리의 줄리아 로빈슨은, 지수함수⁠(exponential function)⁠만큼 빨리 자라는 관계 하나를 정수 계수 방정식으로 적을 수 있으면 지수 자체도 그렇게 적힌다는 것을 보였습니다. 1961년 데이비스, 퍼트넘, 로빈슨은 미지수가 지수 자리에도 들어가는 방정식이라면 정수해를 판정하는 알고리즘이 없다는 것을 증명했습니다. 남은 일은 지수를 보통의 다항식으로 적는 것이었습니다. 레닌그라드의 스테클로프 수학 연구소 분원에 있던 마티야세비치가 피보나치 수열⁠(Fibonacci sequence)⁠이 자라는 방식을 이용해 1970년 1월 마지막 조각을 맞추었습니다. 그해 가을부터 로빈슨과 마티야세비치는 편지로 함께 연구했습니다. 로빈슨은 1975년 여성 수학자로는 처음 미국 국립 과학원 회원이 되었고, 1983년 미국 수학회의 첫 여성 회장이 되었습니다.

판정할 수 없는 문제는 논리 밖에서도 잇달아 나타났습니다. 1946년 포스트는 이런 문제를 판정할 수 없음을 보였습니다. 위아래 칸에 글자열이 적힌 도미노 몇 종류를 받아, 위 칸을 이어 붙인 글자열과 아래 칸을 이어 붙인 글자열이 같아지게 늘어놓을 수 있는지 묻는 문제입니다(포스트 대응 문제⁠, Post correspondence problem⁠). 이듬해 포스트와 소련의 안드레이 마르코프는 따로, 양쪽으로 쓸 수 있는 글자 바꾸기 규칙이 주어졌을 때 두 낱말이 서로 바뀌는지를 판정할 수 없는 경우를 찾았습니다. 이 마르코프는 「다음 단어를 맞히는 기계」 1절에 나오는 마르코프의 아들입니다. 1911년 무렵 막스 덴은 군에서 같은 모양의 문제를 물었습니다. 군은 되돌릴 수 있는 연산들과 그 연산을 이어 붙이는 규칙의 체계이고, 정육면체 퍼즐의 돌리기들이 한 예입니다. 덴의 문제는 두 연산의 나열이 같은 결과를 내는지 가려내는 것이었고, 1950년대에 소련의 표트르 노비코프와 미국의 윌리엄 분이 따로 이것도 판정할 수 없는 경우가 있음을 보였습니다.

흔히 판정할 수 없는 것은 '멈추는가'라는 특별한 질문 하나뿐이라고 생각하지만, 그렇지 않습니다. 1953년 헨리 라이스는 가장 넓은 결론을 냈습니다. 프로그램의 성질 가운데 입력과 출력의 관계에만 달린 것은, 모든 프로그램이 가지거나 어떤 프로그램도 갖지 않는 뻔한 경우가 아니면 모두 판정할 수 없다는 것입니다(라이스의 정리⁠, Rice's theorem⁠). 예를 들어 "이 프로그램은 언제나 정렬된 목록을 내놓는가"를 모든 프로그램에 대해 옳게 가려내는 검사기는 없습니다.

6 · 이론이 기계를 만나다전쟁, 진공관, 그리고 모방 게임⁠(imitation game)⁠

이 절은 역사를 따라갑니다. 물음은 이것입니다. 종이 위의 사고 실험⁠(thought experiment)⁠이던 보편 기계는 어떻게 실제 기계가 되었고, 그 기계를 두고 사람들은 무엇을 묻기 시작했을까?

튜링 기계는 종이 위의 사고 실험이었습니다. 그것이 실제 기계가 되기까지는 전쟁이 끼어 있었습니다. 그보다 앞선 꿈도 있었습니다. 100년 앞서 런던의 수학자 찰스 배비지가 해석기관⁠(Analytical Engine)⁠을 구상했습니다. 천공 카드⁠(punched card)⁠로 명령을 받아 어떤 순서의 계산이든 해내도록 설계한, 증기로 돌리는 톱니바퀴 계산기였습니다. 1843년 에이다 러브레이스는 이 기계를 소개하는 글의 주석에 기계가 베르누이 수⁠(Bernoulli numbers)⁠를 계산하는 절차를 한 단계씩 적어 두었습니다. 베르누이 수는 $1^k + 2^k + \cdots + n^k$ 같은 거듭제곱의 합을 식으로 나타낼 때 계수로 나오는 수들로, 야코프 베르누이의 이름이 붙어 있습니다. 그러나 해석기관은 끝내 완성되지 않았습니다.

러브레이스의 글이 나온 사정은 이렇습니다. 1840년 배비지는 이탈리아 토리노의 학자 모임에서 해석기관을 설명했고, 그 자리에 있던 공병 장교 루이지 메나브레아가 1842년 제네바의 학술지에 프랑스어로 해설을 실었습니다. 러브레이스는 이 글을 영어로 옮기면서 원문보다 훨씬 긴 주석 일곱 개(A부터 G까지)를 붙여 1843년에 냈습니다. 베르누이 수를 계산하는 절차는 마지막 주석 G에 있습니다. 같은 주석에서 그는 해석기관이 무언가를 새로 만들어 낸다고 내세우지 않으며, 우리가 시키는 법을 아는 일은 무엇이든 할 수 있다고 적었습니다. 100여 년 뒤 튜링이 '러브레이스 부인의 반론'이라 부른 것이 이 대목입니다. 배비지가 그보다 먼저 구상한 차분기관은 다항식의 차분⁠(finite difference)⁠으로 수표를 만드는 기계입니다(배비지가 이 기계를 구상한 사정은 「한 점에서 전부를」 6절에 나옵니다). 1991년 런던 과학 박물관이 그의 설계도대로 차분기관 2호기를 만들어 실제로 계산해 보였습니다.

전쟁은 계산을 암호 해독의 무기로 만들었습니다. 2차 세계대전 동안 튜링은 블레츨리 파크에서 봄베⁠(bombe)⁠를 설계했습니다. 독일군의 회전자 암호기 에니그마⁠(Enigma)⁠가 그날 어떤 설정으로 맞춰져 있는지, 가능한 설정을 전기기계식으로 빠르게 훑어 찾아내는 장치였습니다. 그 이야기는 「나머지로 지키는 비밀」에 있습니다. 1944년 블레츨리에서는 우체국 기술자 토미 플라워스가 만든 콜로서스⁠(Colossus)⁠가 독일군 최고 사령부의 로렌츠 암호⁠(Lorenz cipher)⁠를 분석하기 시작했습니다. 로렌츠 암호는 독일 로렌츠 사의 전신 암호기로 만든 암호로, 「나비의 날갯짓」의 기상학자 에드워드 로렌츠와는 관계가 없습니다. 콜로서스는 진공관 약 1,600개(뒤의 개량형은 2,400개)로 만든 전자식 기계였지만, 한 가지 일에 맞춰 만든 기계였습니다. 진공관은 유리관 속 전자의 흐름을 켜고 꺼서 스위치 노릇을 하는 부품입니다.

보편 기계의 생각이 하드웨어가 된 것은 전쟁 막바지의 미국에서였습니다. 필라델피아의 펜실베이니아 대학 무어 스쿨에서는 전기공학자 J. 프레스퍼 에커트와 물리학자 존 모클리가 포탄 궤도⁠(orbit)⁠를 계산하려고 ENIAC을 만들었습니다. 진공관 1만 7천여 개로 된 전자식 계산기였지만, 프로그램을 바꾸려면 전선을 뽑아 다시 꽂아야 했습니다. 이 팀에 자문으로 합류한 폰 노이만은 1945년 6월 후속 기계 EDVAC의 설계를 정리한 「EDVAC 보고서 초안」을 썼습니다. 핵심은 프로그램을 데이터와 같은 기억 장치에 넣는다는 것, 곧 저장 프로그램입니다. 규칙표를 테이프에 적는 튜링의 보편 기계와 같은 생각입니다. 그해 폰 노이만은 이 기계를 위해 숫자 계산이 아닌 일을 하는 프로그램을 손으로 적었습니다. 정렬된 두 목록을 하나로 합쳐 정렬된 목록 하나를 만드는 병합 프로그램입니다. 뒷날 컴퓨터 과학자 도널드 크누스는 이것을 저장 프로그램 컴퓨터⁠(stored-program computer)⁠를 위해 쓰인 가장 이른 프로그램 가운데 하나로 꼽았습니다(「줄 세우기의 한계」 3절).

ENIAC이 필요했던 까닭은 표였습니다. 포병이 포를 쏘려면 거리와 바람과 포탄 종류마다 포신을 얼마나 들어야 하는지 적은 사격표가 있어야 했고, 표의 한 줄은 포탄의 궤도를 미분방정식⁠(differential equation)⁠, 곧 위치와 속도⁠(velocity)⁠처럼 어떤 양과 그 양이 변하는 빠르기 사이의 관계로 주어진 방정식을 한 걸음씩 풀어야 얻어졌습니다. 메릴랜드의 애버딘 성능시험장과 무어 스쿨에서는 주로 여성인 계산원들이, 다시 말해 4절에서 말한 사람 'computer'들이 탁상 계산기로 이 일을 했습니다. 기계도 이미 있었습니다. 1절에서 섀넌이 다루던 부시의 미분 해석기는 미분방정식을 톱니와 회전축으로 푸는 방 하나 크기의 계산기였습니다. 수를 숫자로 적지 않고 축이 돈 각도 같은 연속적인 양으로 나타내는 아날로그 계산기입니다. 60초 동안 날아가는 궤도 하나에 사람은 20시간쯤, 부시의 설계를 본뜬 미분 해석기는 15분쯤 걸렸고, ENIAC은 30초에 해냈다고 전합니다. 이 계산원들 가운데 케이 맥널티, 진 제닝스, 베티 스나이더, 말린 웨스코프, 프랜시스 빌라스, 루스 리히터먼 여섯 명이 ENIAC의 첫 프로그래머가 되었습니다. 기계는 전쟁이 끝난 뒤에야 완성되어 1946년 2월에 공개되었습니다. 공개보다 앞선 1945년 말에 처음 맡은 큰 일은 로스앨러모스의 수소 폭탄 설계를 위한 계산이었습니다. 1950년 이 기계로 처음 계산한 일기 예보의 이야기는 「나비의 날갯짓」에 있습니다.

이 생각이 누구의 것인지는 복잡합니다. 폰 노이만은 튜링의 논문을 알고 있었고, 동료의 회고에 따르면 그 중요성을 여러 번 강조했습니다. 다만 보고서에 폰 노이만의 이름만 실린 탓에 에커트와 모클리의 몫이 가려졌다는 논란은 지금도 이어집니다. 오늘날 대부분의 컴퓨터는 계산하는 처리 장치와, 프로그램과 데이터를 함께 담는 기억 장치를 나누어 두고 둘 사이로 명령과 데이터를 주고받는데, 이 구조를 '폰 노이만 구조⁠(von Neumann architecture)⁠'라고 부릅니다.

첫 저장 프로그램⁠(stored program)⁠ 기계는 영국에서 돌았습니다. 튜링은 1946년 초 테딩턴의 국립 물리 연구소에 저장 프로그램 컴퓨터 ACE(자동 계산 기관)의 상세한 설계를 냈지만, 제작은 늦어졌습니다. 먼저 돌아간 것은 맨체스터 대학의 전기공학자 프레더릭 윌리엄스와 톰 킬번이 만든 작은 실험 기계, 흔히 '맨체스터 베이비'라 불리는 기계였습니다. 1948년 6월 21일 이 기계가 처음 실행한 저장 프로그램은 $2^{18} = 262{,}144$의 가장 큰 진약수(자기 자신을 뺀 약수⁠(divisor)⁠)를 뺄셈만으로 찾는 프로그램이었고, 52분이 걸렸다고 알려져 있습니다. 같은 해 튜링은 맨체스터로 옮겼고, 뒤에 페란티 마크 1의 프로그래밍 설명서를 썼습니다. 영국 전기 회사 페란티가 이 기계를 이어 상업용으로 내놓은 컴퓨터입니다. 1949년 5월에는 무어 스쿨 강의를 듣고 돌아간 케임브리지의 물리학자 모리스 윌크스가 만든 EDSAC이 돌기 시작했습니다.

같은 무렵 대서양 건너편에서는 기계가 다룰 대상에 이름이 붙었습니다. 1절의 섀넌은 1948년 벨 연구소에서 논문 「통신의 수학적 이론」을 발표해, 정보를 재는 단위 '비트'와 정보 엔트로피⁠(information entropy)⁠를 내놓았습니다. 1비트는 똑같이 그럴듯한 두 가능성(동전의 앞과 뒤) 가운데 하나를 알려 주는 정보의 양이고, '비트'라는 이름은 동료였던 통계학자 존 튜키가 binary digit(이진 숫자)를 줄여 지었습니다. 엔트로피⁠(entropy)⁠는 한 글자가 평균⁠(mean)⁠ 몇 비트의 정보를 담는지를 재는 양입니다. 섀넌이 이 엔트로피로 영어 글의 정보량을 잰 이야기는 「말을 세는 기계」 5절에 있습니다. 엔트로피가 어떤 무손실 압축⁠(lossless compression)⁠도 넘을 수 없는 한계라는 원천 부호화 정리⁠(source coding theorem)⁠와, 거꾸로 여분을 더해 잡음을 이기는 부호의 이야기는 「짧게 보내기」에 있습니다. 불의 0과 1이 회로가 되고, 회로가 정보의 단위가 된 것입니다.

1930년부터 오늘까지. 1930년대에 유럽의 논리학자들이 프린스턴으로 모이고, 전쟁 뒤에는 필라델피아의 설계가 케임브리지와 맨체스터로 건너가며, 1970년대의 복잡도 이론이 토론토·버클리·모스크바에서 따로 태어나는 것을 보세요.

나는 '기계는 생각할 수 있는가?'라는 질문을 생각해 보자고 제안한다.— 앨런 튜링, 「계산 기계와 지능」, 『마인드』(1950)의 첫 문장

'생각'이라는 말의 뜻을 따지는 대신, 튜링은 질문을 모방 게임으로 바꾸었습니다. 질문자가 글로만 대화하며 상대가 사람인지 기계인지 가려내게 하고, 기계가 얼마나 잘 속이는지를 보자는 것입니다. 그는 50년쯤 뒤에는 기억 용량⁠(capacity)⁠이 $10^9$비트쯤 되는 컴퓨터가 이 게임을 잘 해서, 보통의 질문자가 5분 동안 묻고 나서 맞게 가려낼 확률⁠(probability)⁠이 70%를 넘지 못할 것이라고 예측했습니다. 이 논문은 신학적 반론, 수학적 반론(곧 괴델의 정리), 의식에서 나온 반론, 기계는 시킨 일밖에 못 한다는 '러브레이스 부인의 반론' 같은 예상 반론을 하나씩 다룹니다. 지금 이 질문이 어디까지 왔는지는 8절에서 다시 봅니다.

7 · 풀 수 있지만 너무 오래 걸리는P 대 NP

이 절의 물음은 이것입니다. 원리적으로는 풀 수 있는 문제 가운데에도, 답을 확인하기는 쉬운데 찾기는 너무 오래 걸리는 문제가 정말 있을까?

정지 문제는 원리적으로 풀 수 없는 문제였습니다. 컴퓨터가 흔해지자 다른 한계가 눈에 들어왔습니다. 원리적으로는 풀 수 있지만 너무 오래 걸리는 문제입니다. 1956년 3월 괴델은 암으로 입원한 폰 노이만에게 편지를 보냈습니다. 주어진 명제에 길이가 $n$ 이하인 증명이 있는지를 기계로 찾는다고 합시다. 괴델은 그 걸음 수를 $n$이나 $n^2$에 비례하는 정도로 줄일 수 있다면, 예·아니오로 답하는 수학 문제에서 수학자의 머리 쓰는 일을 기계가 완전히 대신할 수 있을 것이라고 썼습니다. 폰 노이만은 이듬해 세상을 떠났고, 이 편지는 1980년대 말에야 널리 알려졌습니다. 오늘날의 말로 하면 그것이 P 대 NP 문제⁠(P versus NP problem)⁠입니다.

한 가지 예로 확인해 봅시다. 손으로 먼저 해 보면, 수 3, 5, 8, 13 가운데 몇 개를 골라 합을 16으로 맞출 수 있을까요? 3 + 13 = 16이 되고, 3 + 5 + 8 = 16도 됩니다. 누가 "3과 13"이라고 알려 주면 덧셈 한 번으로 확인이 끝나지만, 아무 말 없이 찾으려면 고르는 방법을 이것저것 해 봐야 합니다. 이것을 부분집합 합 문제라 합니다.

아래 그림으로 더 큰 문제를 풀어 봅시다. 수 개가 있습니다. 그중 몇 개를 골라 더해서 목표 에 정확히 맞출 수 있을까요? 수를 눌러 고르거나 빼 보세요. 지금 고른 수의 합은 입니다.

누군가 답을 건네주면 확인은 덧셈 몇 번이면 끝납니다. 찾는 일은 다릅니다. 가장 단순한 방법은 가능한 부분집합을 모두 훑는 것인데, 그 수는 개입니다. ▶ 모두 훑기 비우기 새 문제

수가 하나 늘 때마다 부분집합의 수는 두 배가 됩니다. 새 수를 고르는 경우와 고르지 않는 경우로 기존의 모든 선택이 둘로 갈라지기 때문입니다(멱집합⁠, power set⁠). 수가 10개면 1,024가지, 20개면 1,048,576가지입니다. 오른쪽 그림에서 수의 개수를 늘려 보세요: $n =$ . 부분집합은 개이고, 1초에 10억 개를 확인하는 컴퓨터로 모두 훑는 데 걸리는 시간은 입니다.

오른쪽 그림의 세로축은 로그 눈금입니다. 눈금이 한 칸 올라갈 때마다 값이 10배가 되도록 그린 축이라, 아주 큰 수와 작은 수를 한 그림에 담을 수 있습니다. 모두 훑는 곡선은 로그 눈금에서 직선인 지수함수이고, 확인하는 곡선과 n³ 같은 다항식은 거의 눕습니다. 더 빠른 컴퓨터로는 해결되지 않습니다. 컴퓨터가 1,000배 빨라져도 같은 시간에 다룰 수 있는 n은 10쯤 늘어날 뿐입니다. $2^{10} \approx 1{,}000$이기 때문입니다. 정리하면, 확인은 빠르고, 모두 훑어서 찾는 일은 수가 늘수록 폭발적으로 느려집니다.

이 차이를 이론으로 다루려면 먼저 '빠르다'를 정의해야 했습니다. 1965년 뉴욕주 스케넥터디의 제너럴 일렉트릭 연구소에 있던 유리스 하르트마니스와 리처드 스턴스는 논문 「알고리즘의 계산 복잡도⁠(computational complexity)⁠에 대하여」에서 문제의 어려움을 튜링 기계가 쓰는 걸음 수로 재고, 걸음을 더 많이 허락하면 풀 수 있는 문제가 실제로 늘어난다는 것을 대각선 논법으로 보였습니다. '계산 복잡도'라는 분야의 이름이 이 논문에서 자리 잡았고, 두 사람은 1993년 튜링상⁠(Turing Award)⁠을 받았습니다.

같은 무렵부터 미국 국립표준국의 수학자 잭 에드먼즈와 IBM의 앨런 코범 같은 연구자들은 걸음 수가 입력 크기의 다항식으로 묶이는 알고리즘을 '효율적'이라고 부르자고 제안했습니다. 에드먼즈의 제안이 실린 1965년 논문은 그래프에서 가장 큰 짝짓기, 곧 최대 매칭⁠(maximum matching)⁠을 다항식 걸음 안에 찾는 알고리즘을 다룬 것이었습니다(「짝을 찾는 알고리즘」 7절).

입력 크기는 문제 하나를 적는 데 드는 기호의 수입니다. 부분집합의 합이라면 수들과 목표를 적는 데 드는 자릿수의 합입니다. 수의 개수만이 아니라 수의 크기도 들어간다는 점에 주의하세요. 수의 개수가 같아도 수가 클수록, 다시 말해 자릿수가 많을수록 입력이 큽니다. 다항식으로 묶인다는 것은 입력 크기가 $n$일 때 걸음 수가 어떤 고정된 지수 $k$에 대해 $n^k$의 상수배를 넘지 않는다는 뜻입니다. 입력이 두 배가 될 때 걸음 수가 $2^n$처럼 폭발하지 않고, $n^2$, $n^3$처럼 일정한 배수(4배, 8배)로만 늘어나는 알고리즘입니다(점근 표기법⁠, asymptotic notation⁠). 숫자로 비교하면, n이 10에서 20으로 늘 때 $n^2$은 100에서 400으로 늘지만 $2^n$은 1,024에서 1,048,576으로 늘어납니다.

이제 두 모임을 정의할 수 있습니다. 이런 알고리즘으로, 곧 다항식만큼의 걸음(다항 시간⁠, polynomial time⁠) 안에 풀리는 예·아니오 문제들의 모임이 P입니다. 답이 '예'일 때 그 근거(부분집합의 합이라면 고른 수들)를 건네받으면 다항 시간에 확인할 수 있는 문제들의 모임이 NP입니다. 부분집합의 합은 NP에 속합니다. 고른 수를 건네받으면 더해서 목표와 비교하기만 하면 되니까요. P의 문제는 근거 없이도 풀 수 있으니 모두 NP에도 속합니다.

비슷해 보이는 두 문제로 차이를 느껴 봅시다. "수들 가운데 두 개를 골라 목표를 맞출 수 있는가"는 P에 속합니다. 두 개를 고르는 방법은 수가 n개일 때 n(n − 1)/2가지뿐이라, 모두 해 봐도 n²보다 적은 걸음이면 됩니다. 수가 20개면 190가지입니다. 반면 "몇 개든 골라 맞출 수 있는가"는 고르는 방법이 $2^n$가지로 폭발합니다. 확인은 둘 다 쉽습니다.

모두 훑는 것보다 빠른 방법이 없지는 않습니다. 수들을 두 무리로 나눠 각 무리에서 만들 수 있는 합을 따로 모은 뒤 서로 맞춰 보면, 대략 $2^{n/2}$걸음이면 됩니다. 목표가 작은 수라면, 0부터 목표까지의 합 하나하나를 만들 수 있는지 표에 차례로 채워 가는 방법으로 대략 (수의 개수) × (목표)걸음에 끝낼 수도 있습니다. 하지만 둘 다 입력 크기의 다항식으로 묶이지 않습니다. 앞의 방법은 여전히 지수만큼 걸리고, 뒤의 방법은 목표가 한 자리 늘 때마다 표가 10배로 커집니다. 걸음 수가 입력 크기(수의 개수와 자릿수)의 다항식으로 묶이는 방법이 있는지는 아무도 모릅니다.

NP는 '비결정적 다항 시간'의 줄임말입니다. 갈림길마다 맞는 쪽을 알아서 골라 주는 가상의 기계라면 다항 시간에 풀 수 있다는 뜻이고, 이것은 '맞는 근거를 건네받으면 다항 시간에 확인할 수 있다'와 같은 말입니다. 흔히 NP를 '다항 시간에 풀 수 없는 문제'의 줄임말로 오해하지만, 그렇지 않습니다. P도 NP 안에 들어 있고, NP의 문제가 모두 어려운지는 바로 아래의 열린 문제입니다.

그다음 발견은 NP 안에 '가장 어려운' 문제들이 있다는 것이었습니다. 1971년 토론토 대학의 컴퓨터 과학자 스티븐 쿡은 충족 가능성 문제⁠(Boolean satisfiability problem)⁠가 NP의 모든 문제를 품고 있다는 것을 보였습니다. 충족 가능성 문제는 논리식의 변수들에 참과 거짓을 알맞게 넣어 식 전체를 참으로 만들 수 있는지 묻는 문제입니다. 예를 들어 "(x 또는 y) 그리고 (x가 아님)"은 x를 거짓, y를 참으로 두면 참이 되므로 '예'이고, "x 그리고 (x가 아님)"은 어떻게 넣어도 거짓이므로 '아니오'입니다. 변수가 n개이면 참·거짓을 넣는 방법이 $2^n$가지라서, 부분집합의 합처럼 모두 해 보는 방법은 폭발합니다.

'품고 있다'가 무슨 뜻인지 작은 예로 먼저 봅시다. 지도의 나라들을 두 색(빨강, 파랑)으로 칠하되 이웃한 나라끼리는 색이 달라야 한다고 합시다. 이 '두 색 칠하기' 문제의 한 사례를 충족 가능성 문제로 바꿔 적을 수 있습니다. 나라마다 변수를 하나 두고, 참이면 빨강, 거짓이면 파랑이라고 읽습니다. 이웃한 두 나라 a, b마다 "(a 또는 b) 그리고 (a가 아님 또는 b가 아님)"을 붙입니다. 앞 괄호는 '둘 중 적어도 하나는 빨강', 뒤 괄호는 '둘 중 적어도 하나는 파랑'이니, 합치면 '둘의 색이 다르다'입니다. 이웃 관계마다 이런 조각을 '그리고'로 모두 이으면, 식 전체를 참으로 만드는 방법이 곧 올바른 칠하기입니다.

손으로 확인해 봅시다. 나라 a, b, c가 한 줄로 이어져 a–b, b–c만 이웃이면, a와 c를 참(빨강), b를 거짓(파랑)으로 두어 식이 참이 되고, 실제로 빨강–파랑–빨강으로 칠할 수 있습니다. 셋이 서로 모두 이웃이면(a–b, b–c, c–a) 식은 어떻게 넣어도 거짓이고, 실제로 두 색으로는 칠할 수 없습니다. 셋 가운데 두 나라는 같은 색이 될 수밖에 없기 때문입니다. 바꿔 적는 일은 이웃 관계 하나마다 조각 하나를 쓰는 것이라 금방 끝나고(다항 시간), 두 질문의 답은 늘 같습니다. 이것이 5절에서 본 환원의 '빠른' 판입니다.

쿡이 보인 것은 이런 바꿔 적기가 NP의 모든 문제에 대해 된다는 것입니다. 착상은 이렇습니다. NP의 문제에는 근거를 확인하는 다항 시간 기계가 있습니다. 그 기계가 걸음마다 무엇을 하는지를 변수들로 적고(몇째 걸음에 몇째 칸에 무엇이 있는가), 규칙표를 지키며 '예'로 끝난다는 조건을 논리식으로 적습니다. 그러면 이 식을 참으로 만드는 방법이 있다는 것은, 기계가 '예'라고 답할 근거가 있다는 것과 같은 말이 됩니다. 걸음 수가 다항식으로 묶여 있으니 식의 길이도 다항식으로 묶입니다.

정확히 말하면, '품고 있다'는 것은 NP의 어떤 문제든 그 한 사례를 다항 시간 안에 충족 가능성 문제의 한 사례로 바꿔 적을 수 있고, 두 사례의 답이 같다는 뜻입니다. 그러니 이 문제를 다항 시간에 푸는 방법이 있으면 NP의 모든 문제를 다항 시간에 풀 수 있습니다. 이처럼 NP에 속하면서 NP의 모든 문제가 그리로 바뀌는 문제를 NP-완전⁠(NP-complete)⁠이라고 합니다. 쿡의 논문 제목은 「정리 증명 절차의 복잡도」였습니다. 그는 기계로 논리식의 증명을 찾는 일이 얼마나 어려운지를 묻고 있었으니, 3절의 결정 문제와 괴델의 편지가 묻던 것을 '얼마나 빨리'라는 말로 다시 물은 셈입니다.

이런 문제는 곧 여기저기서 발견되었습니다. 쿡의 발표 이듬해, 버클리의 컴퓨터 과학자 리처드 카프는 21개의 조합 문제가 모두 NP-완전임을 보였습니다. 이 글에서 본 부분집합의 합을 비롯해, 이웃한 꼭짓점끼리 색이 다르도록 그래프를 주어진 수의 색으로 칠할 수 있는지 묻는 문제, 모든 꼭짓점⁠(vertex)⁠을 한 번씩만 지나 제자리로 돌아오는 길(해밀턴 회로⁠, Hamiltonian cycle⁠)이 있는지 묻는 문제가 모두 그 안에 있습니다. 칠하기 문제라도 색이 둘이면 P에 속하고, 셋 이상이면 NP-완전입니다. 두 색은 한 나라의 색을 정하면 이웃의 색이 차례로 강제되니 따라가기만 하면 되지만, 세 색부터는 그런 지름길이 알려져 있지 않습니다.

카프가 쓴 방법도 환원이었고, 여기서도 방향이 중요합니다. 새 문제 X가 NP-완전임을 보이려면 X가 NP에 속함을 보인 뒤, 이미 NP-완전이라고 알려진 문제를 X로 환원해야 합니다. 그러면 NP의 모든 문제가 먼저 그 문제로, 다시 X로 바뀌니 X도 모든 문제를 품습니다. 방향을 거꾸로 해서 X를 충족 가능성 문제로 바꿔 적는 것은 X가 NP에 속한다는 것을 보일 뿐, X가 어렵다는 것을 보이지 못합니다. 앞의 두 색 칠하기가 바로 그런 예입니다. 충족 가능성 문제로 바꿔 적을 수 있지만 쉬운 문제입니다.

철의 장막 너머 소련에서는 콜모고로프의 제자 레오니트 레빈이 독립적으로 같은 결과에 이르러 1973년에 발표했습니다. 그래서 이 정리는 지금 쿡–레빈 정리⁠(Cook–Levin theorem)⁠라고 불립니다. 레빈의 논문 제목 「보편적인 차례 탐색 문제」에서 '차례 탐색'은 러시아어 페레보르(перебор), 곧 경우를 하나하나 다 해 보기를 옮긴 말입니다. 소련의 연구자들은 1950년대부터 페레보르를 피할 수 없는 문제가 있는지를 따져 왔고, 레빈의 결과는 그 물음에 정확한 모양을 주었습니다. 레빈은 정치적인 이유로 학위를 제때 받지 못했고, 1978년 미국으로 망명했습니다.

그렇다면 P와 NP는 같을까요? 확인이 쉬운 문제는 모두 찾기도 쉬울까요? 대부분의 연구자는 아니라고 믿지만 아무도 증명하지 못했습니다(P 대 NP 문제). 두 답이 각각 무엇을 뜻하는지 적어 두면 이렇습니다. P = NP라면, NP-완전 문제 하나, 예를 들어 부분집합의 합을 다항 시간에 푸는 방법이 있고, 환원을 거쳐 NP의 모든 문제가 다항 시간에 풀립니다. P ≠ NP라면, NP-완전 문제는 어느 것도 다항 시간에 풀리지 않습니다. 그중 하나라도 빨리 풀리면 모두가 빨리 풀릴 테니까요. 어느 쪽이든 NP-완전 문제들은 함께 움직입니다. 2000년 5월 미국의 민간 수학 재단인 클레이 수학 연구소는 이 문제를 100만 달러 상금이 걸린 7개의 밀레니엄 문제 가운데 하나로 발표했습니다. 발표 장소는 파리의 콜레주 드 프랑스였습니다. 100년 전 힐베르트가 23개 문제를 내놓은 바로 그 도시입니다.

정리하면, P는 빨리 풀 수 있는 문제, NP는 답의 근거를 빨리 확인할 수 있는 문제이고, NP-완전 문제는 환원을 통해 NP 전체의 어려움을 한 몸에 지닌 문제입니다. 확인이 쉬우면 찾기도 쉬운지는 아직 아무도 모릅니다.

쿡은 1966년부터 버클리 수학과의 조교수였지만 1970년 재임용되지 못해 토론토로 옮겼고, 이듬해 5월 오하이오주 셰이커하이츠에서 열린 학회에서 이 논문을 발표했습니다. 뒷날 리처드 카프는 버클리 전기공학·컴퓨터과학과의 30주년 기념 연설에서, 수학과를 설득해 그에게 종신 재직권을 주게 하지 못한 것을 "우리의 영원한 수치"라고 했습니다. 쿡은 1982년 튜링상을 받았습니다.

이 질문은 추상적인 것 같지만 우리의 일상을 떠받칩니다. RSA 암호⁠(RSA cryptosystem)⁠와 디피–헬먼 키 교환⁠(Diffie–Hellman key exchange)⁠은 큰 수의 소인수분해나 이산로그⁠(discrete logarithm)⁠가 확인은 쉽고 찾기는 어렵다는 데 기대고 있습니다. 이산로그 문제란 소수 $p$와 수 $g$, 그리고 $g^x$를 $p$로 나눈 나머지가 주어졌을 때 지수 $x$를 찾는 문제입니다(「나머지로 지키는 비밀」). P = NP이고 그 증명이 실용적인 알고리즘을 준다면 이런 암호는 원리적으로 무너집니다. 반대로 P ≠ NP가 증명되어도 이 특정한 문제들이 어렵다는 보장이 저절로 생기지는 않습니다. 소인수분해는 NP-완전인지 알려져 있지 않기 때문입니다. 한편 어떤 수가 소수인지 판정하는 문제가 P에 속한다는 것은 2002년 인도 칸푸르 공과대학의 교수 마닌드라 아그라왈과 그의 두 학생 니라지 카얄, 니틴 삭세나가 보였습니다(소수 판정⁠, primality test⁠).

8 · 마음은 기계인가철학자들의 논쟁

이 절의 물음은 이것입니다. 기계가 원리적으로 풀 수 없는 문제가 있다면, 그것은 사람의 마음이 기계와 다르다는 뜻일까? 이 절은 정리가 아니라 논쟁을 소개합니다. 어느 쪽도 증명으로 끝나지 않았습니다.

계산의 한계를 밝힌 정리들은 곧 사람의 마음을 묻는 질문으로 이어졌습니다. 1939년 케임브리지에서 오스트리아 출신의 철학자 루트비히 비트겐슈타인은 수학의 기초에 관한 강의를 했고, 튜링이 그 강의에 참석했습니다. 학생들의 필기로 남은 기록을 보면, 비트겐슈타인은 체계 속에 모순이 숨어 있다는 것을 왜 그렇게 두려워하느냐고 물었고, 튜링은 모순이 있는 계산을 믿고 지은 다리는 무너질 수 있다는 식으로 맞섰습니다. 비트겐슈타인에게 수학은 규칙을 따르는 사람들의 실천이었고, 괴델의 정리가 수학에 무엇을 말해 주는지에 대해서도 회의적이었습니다.

괴델 자신은 반대편에 있었습니다. 그는 수학의 대상이 사람과 독립적으로 있다고 믿었고, 1951년 강연에서 적어도 둘 중 하나는 참이라고 말했습니다. 사람의 마음이 어떤 기계도 무한히 넘어서거나, 사람이 원리적으로 풀 수 없는 수학 문제가 있거나.

이 이분법⁠(bisection method)⁠의 첫째 갈래를 밀고 나간 사람들이 있었습니다. 1961년 옥스퍼드의 철학자 존 루커스는 한 걸음 더 나아가, 어떤 기계든 그 기계의 괴델 문장을 사람은 참이라고 '볼' 수 있으므로 마음은 기계가 아니라고 주장했습니다. 1989년 영국의 수리물리학자 로저 펜로즈(2020년 노벨 물리학상)가 『황제의 새 마음』에서 비슷한 논증을 폈습니다. 대부분의 논리학자와 철학자는 이 논증을 받아들이지 않습니다. 3절에서 본 대로, 괴델 문장이 참이라고 '보려면' 그 체계에 모순이 없음을 알아야 하는데, 사람이 자기 추론 전체의 무모순성을 안다는 근거가 없다는 것이 대표적인 반론입니다. 논쟁은 지금도 이어집니다.

1980년 버클리의 철학자 존 설은 방향이 다른 반론을 내놓았습니다. 중국어를 모르는 사람이 방 안에서 두꺼운 규칙서만 보고 중국어 질문에 알맞은 중국어 답을 적어 내보낸다면, 밖에서는 방이 중국어를 이해하는 것처럼 보여도 방 안의 누구도 중국어를 이해하지 않는다는 것입니다. 튜링 기계가 하는 일도 기호를 규칙대로 옮기는 것뿐이니, 모방 게임에서 이겨도 이해했다고 할 수 없다는 주장입니다. 방 전체가 이해한다고 보면 된다는 반론을 비롯해 수많은 답이 나왔습니다. 이 논쟁은 글로 대화하는 오늘날의 언어 모델⁠(language model)⁠을 두고 다시 불붙었습니다. 언어 모델은 엄청난 양의 글을 읽혀 다음에 올 낱말을 예측하도록 학습시킨 프로그램입니다. 기계가 말을 어떻게 세고 예측하는지는 「말을 세는 기계」에서, 다음 낱말을 확률로 짐작하는 언어 모델이 어떻게 만들어지고 왜 그럴듯하게 틀리는지는 「다음 단어를 맞히는 기계」에서 이어집니다. 사람이 규칙서를 적는 대신 예를 보며 기계가 스스로 가중치⁠(weight)⁠를 고쳐 가는 신경망⁠(neural network)⁠의 역사는 「배우는 기계」에 있습니다.

라이프니츠의 꿈은 뜻밖의 모양으로 일부 이루어졌습니다. 기계는 모든 명제를 판정하지 못하지만, 사람이 적은 증명을 한 줄씩 검사할 수는 있습니다. 증명을 찾는 기계도 일찍 나왔습니다. 1956년, '인공지능⁠(artificial intelligence)⁠'이라는 이름이 자리 잡은 다트머스 여름 모임(「배우는 기계」) 무렵에 앨런 뉴얼, 허버트 사이먼, 클리프 쇼의 프로그램 '논리 이론가'는 2절의 『수학 원리』 2장의 처음 정리 52개 가운데 38개를 증명했고, 그중 *2.85에는 책보다 깔끔한 증명을 찾아냈습니다. 사이먼이 그 증명을 보여 주자 러셀은 기뻐했다고 전합니다. 1959년 무렵 논리학자 하오 왕은 IBM 704에서 돌린 프로그램으로 『수학 원리』에 실린, '모든'과 '어떤'이 들어간 논리(3절의 1차 논리⁠(first-order logic)⁠)의 정리 350여 개를 9분이 안 되는 시간에 모두 증명했습니다. 다만 이런 프로그램도 3절의 결정 문제를 피해 가지는 못합니다. '모든'과 '어떤'이 들어간 논리에서 증명이 있으면 언젠가 찾아내지만, 증명이 없을 때 없다고 늘 알려 줄 수는 없습니다.

1976년 일리노이 대학의 수학자 케네스 아펠과 볼프강 하켄은 컴퓨터로 2,000가지 가까운 배치를 확인해 4색 정리⁠(four color theorem)⁠를 증명했고, 사람이 손으로 확인할 수 없는 증명을 증명으로 인정할지를 두고 논쟁이 일었습니다. 오늘날에는 증명 보조기⁠(proof assistant)⁠라는 프로그램이 증명의 모든 단계가 공리와 추론 규칙에서 정말 따라 나오는지를 기계적으로 확인하고, 5절의 바쁜 비버 값도 그렇게 검증되었습니다. 찾는 일은 사람에게, 확인하는 일은 기계에게. 이것은 P와 NP의 구분과 같은 모양입니다.

9 · 이어지는 길계산이 닿는 곳

'기계로 할 수 있는 일'이라는 개념은 수학 안팎의 여러 분야로 이어집니다.

• 언어: 테이프를 한 방향으로 읽어 나가기만 하고 쓰지 못하는 기계는 유한 오토마톤⁠(finite automaton)⁠이 되고, 그 기계가 알아보는 패턴을 적는 방법이 정규 표현식⁠(regular expression)⁠입니다. 여기에 스택⁠(stack)⁠, 곧 접시 더미처럼 맨 위에만 넣고 뺄 수 있는 기억 장치 하나를 더하면 문맥 자유 문법⁠(context-free grammar)⁠을 다룰 수 있습니다. 기계의 힘에 따라 언어를 층층이 나눈 촘스키 위계⁠(Chomsky hierarchy)⁠의 맨 위층이 튜링 기계입니다. 「말을 세는 기계」로 이어집니다. 정규 표현식은 1951년 처치의 제자 스티븐 클리니가 워런 맥컬러와 월터 피츠의 신경 그물이 알아볼 수 있는 입력을 분석하다 만든 것이고(「배우는 기계」 1절), 그때 쓴 표 채우기가 최단 경로⁠(shortest path)⁠ 알고리즘과 같은 뼈대라는 것은 「같은 계산, 다른 덧셈」에 있습니다.
• 불가능의 증명: 정지 문제는 '없다'를 대각선으로 증명한 예입니다. 각의 삼등분, 5차방정식의 근의 공식⁠(quadratic formula)⁠, 공정한 투표 규칙처럼 서로 먼 분야의 불가능성 증명들이 불변량⁠(invariant)⁠, 세기, 대각선이라는 세 가지 무기로 나뉜다는 것은 「불가능의 증명」에서 볼 수 있습니다. 마티야세비치의 정리처럼 한 문제의 불가능을 다른 문제로 옮겨 퍼뜨리는 환원도 거기서 다룹니다.
• 짧은 설명: 문자열을 출력하는 가장 짧은 프로그램의 길이, 곧 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠는 계산할 수 없습니다. 그것을 계산하는 기계가 있으면 정지 문제를 풀 수 있기 때문입니다. 과학 이론을 자료의 가장 짧은 설명으로 보는 생각이 어디까지 정리이고 어디부터 철학인지는 「압축하는 것이 이해하는 것이다」 4절에 있습니다.
• 게임: "이 명제는 참인가"는 두 사람의 게임으로 읽을 수 있습니다. '모든'은 상대가 고르는 수이고 '어떤'은 내가 고르는 수입니다. 1912년 케임브리지 국제수학자대회에서 체르멜로가 체스는 이미 승패가 정해진 게임이라는 것을 보인 이야기와, 논리가 두 구조를 구별할 수 있는지를 게임으로 재는 방법은 「이기는 쪽이 존재한다」에 있습니다.
• 틀린 증명: 러셀의 편지가 무너뜨린 프레게의 다섯째 기본 법칙, 그리고 수학자들이 사람의 검토만으로는 믿기 어려워진 증명을 증명 보조기로 검사하게 된 사정은 「틀린 증명이 만든 수학」에 있습니다.
• 무한: 프로그램은 셀 수 있지만 실수⁠(real number)⁠는 셀 수 없으므로, 프로그램으로 계산할 수 있는 실수는 가산 개뿐이고 나머지 셀 수 없이 많은 실수는 어떤 프로그램으로도 계산할 수 없습니다. 정지 문제의 대각선은 칸토어의 대각선이 계산의 세계로 옮겨 온 것입니다(「무한에도 크기가 있다」, 집합의 크기⁠(cardinality)⁠).
• 그래프: 그래프의 모든 변을 한 번씩 지나는 오일러 경로⁠(Euler path)⁠는 그래프가 이어져 있는지 보고 꼭짓점마다 붙은 변의 수(차수)가 홀수인 꼭짓점이 0개나 2개인지 세기만 하면 판정되는 쉬운 문제이고, 모든 꼭짓점을 한 번씩 지나는 해밀턴 회로는 NP-완전입니다(P 대 NP 문제). 비슷해 보이는 두 문제가 계산의 세계에서는 멀리 떨어져 있습니다(「일곱 다리의 도시」). 두 지점 사이의 최단 경로는 쉽지만, 모든 도시를 한 번씩 도는 가장 짧은 길을 찾는 외판원 문제⁠(traveling salesman problem)⁠는 NP-완전 문제만큼 어렵습니다.
• 정수론⁠(number theory)⁠: 방정식의 정수해를 판정하는 알고리즘이 없다는 마티야세비치의 정리는 정지 문제가 다항식의 세계 안에도 숨어 있다는 뜻입니다. 그 부산물로, 변수들에 자연수를 넣었을 때 나오는 양의 값을 모두 모으면 정확히 소수 전체가 되는 다항식도 만들 수 있습니다. 1976년에는 변수 26개짜리 그런 다항식이 실제로 적혔습니다. 괴델 수가 소인수분해의 유일성에 기댄 것도 같은 연결입니다(소수가 곱셈의 원자라는 이야기부터 시작하는 「소수를 세는 사람들」).
• 예측: 로렌츠의 방정식(로렌츠 끌개⁠, Lorenz attractor⁠)은 계산할 수 있지만 오래 앞을 내다볼 수는 없습니다. 초기값의 작은 오차가 기하급수적으로 커지는 혼돈⁠(chaos)⁠은 정지 문제와는 다른 종류의 한계입니다(「나비의 날갯짓」).
• 증명: 람다 계산의 변수마다 타입을 붙이면 모든 계산이 반드시 끝나는 대신 계산할 수 있는 함수를 모두 적을 수는 없게 됩니다. 이때 타입은 명제로, 프로그램은 그 명제의 증명으로 읽힙니다(단순 타입 람다 계산⁠(simply typed lambda calculus)⁠, 커리–하워드 대응⁠(Curry–Howard correspondence)⁠). Coq나 Lean 같은 증명 보조기가 이 대응 위에 서 있습니다(「증명은 프로그램이다」). 끝나지 않을 수 있는 타입 없는 프로그램에는 '아직 모름'을 뜻하는 값 ⊥('바닥')에서 시작해 한 번 더 계산할 때마다 조금씩 더 아는 근삿값을 쌓아 올리고, 더는 바뀌지 않는 첫 값, 곧 최소 고정점으로 뜻을 주는데, 이것이 영역 이론⁠(domain theory)⁠입니다. 한 프로그램이 명세(약속한 입출력 관계)를 지킨다는 것은 반복문마다 불변식(반복이 도는 내내 참으로 남는 조건)과 줄어드는 양을 적어 호어 논리⁠(Hoare logic)⁠로 증명합니다. 정지 문제 때문에 이 일을 모든 프로그램에 대해 자동으로 할 수는 없어서, 불변식은 대개 사람이 적어 줍니다.
• 독립성: 불완전성 정리의 '증명할 수 없는 문장'은 공리에서 독립⁠(independence)⁠인 명제, 곧 그 공리들로 증명할 수도 없고 그 부정을 증명할 수도 없는 명제의 한 예입니다. 유클리드의 평행선 공준⁠(parallel postulate)⁠이 나머지 공리에서 독립이라는 발견이 가장 이름난 선례입니다(「평행선의 반란」).