20세기 초 수학자들에게는 원대한 꿈이 있었다. 모순을 일으키지 않는 일관성(consistency)을 갖추고, 동시에 참인 모든 수학적 사실을 이끌어낼 수 있는 완전성(completeness)을 지닌 공리 체계를 마련하는 것이었다. 이 기초 위에 수학 전체를 흔들림 없이 쌓아 올릴 수 있으리라는 기대였다. 그러나 1931년, 25세의 오스트리아 논리학자 쿠르트 괴델이 발표한 불완전성 정리는 그 꿈을 무너뜨렸다. 그는 수학의 토대로 삼을 수 있는 어떤 공리 집합도 반드시 불완전하며, 그 공리로는 증명할 수 없는 참인 명제가 항상 존재한다는 것을 보였다. 게다가 어떤 공리 집합도 자기 자신의 일관성을 증명할 수 없다는 것까지 함께 증명했다.
이 결론이 뜻하는 바는 분명하다. 증명 가능한 것과 참인 것을 하나로 통합하는 '수학의 만물이론'은 존재할 수 없다는 것이다. 수학자가 무엇을 증명할 수 있는가는 모든 답이 흘러나오는 근원적 진리가 아니라, 그가 어떤 가정에서 출발했는가에 달려 있다. 발표 이후 89년 동안 수학자들은 괴델의 정리가 예고한 바로 그런 '답할 수 없는 질문'들과 실제로 마주쳤다. 무한의 크기를 다루는 연속체 가설, 그리고 컴퓨터과학의 근간인 정지 문제(halting problem)가 대표적이며, 물리학에서도 결정 불가능한 문제가 등장했다.
문장을 숫자로 바꾸는 괴델 넘버링
괴델 증명의 핵심 전략은, 공리 체계에 '대한' 진술을 그 체계 '안의' 진술, 즉 숫자에 관한 진술로 사상(map)한 것이다. 이렇게 하면 하나의 공리 체계가 자기 자신에 대해 조리 있게 말할 수 있게 된다. 어니스트 네이글과 제임스 뉴먼이 1958년 저서에서 정리한 방식을 보면, 우선 기본 공리를 표현하는 12개의 기초 기호에 1부터 12까지의 번호를 붙인다. 존재를 뜻하는 ∃, 덧셈의 +, '~의 다음 수'를 뜻하는 s 같은 것들이다. 변수 x, y, z는 12보다 큰 소수(13, 17, 19…)에 대응시킨다.
그다음이 정교하다. 기호들의 임의의 조합, 즉 어떤 수식이든 고유한 숫자 하나로 바꾼다. 예를 들어 0 = 0은 기호가 각각 6, 5, 6에 대응하므로, 처음 세 소수 2·3·5를 각 위치의 기호 번호만큼 거듭제곱해 곱한다. 즉 2⁶ × 3⁵ × 5⁶ = 243,000,000이 된다. 정수는 오직 한 가지 방식으로만 소인수분해되기 때문에, 이 숫자를 되돌리면 반드시 0 = 0이라는 원래 수식만 나온다. 서로 다른 두 수식이 같은 번호를 가질 수 없다는 것, 이 유일성이 전체 논증을 떠받친다. 나아가 수식의 나열, 즉 증명 전체에도 같은 방식으로 고유한 번호를 부여할 수 있다.
자기 자신을 말하는 문장
결정적인 통찰은 '~라는 수식은 증명될 수 없다' 같은 메타수학적 진술마저 다시 숫자에 관한 산술 명제로 번역할 수 있다는 데 있었다. 예컨대 '~(0 = 0)의 첫 기호는 물결표다'라는 참인 진술은, 그 괴델 넘버가 2를 정확히 한 번만 인수로 갖는다는 순수한 산술적 사실로 옮겨진다. 네이글과 뉴먼의 표현대로, 긴 기호열의 타이포그래피적 성질을 커다란 정수의 소인수분해 성질에 관한 이야기로 간접적이지만 완벽하게 정확하게 말할 수 있게 된 것이다.
여기에 괴델은 '치환'이라는 한 수를 더 두었다. 어떤 수식의 괴델 넘버를 그 수식 자신에 대입할 수 있게 한 것이다. 이 장치를 통해 그는 결국 '괴델 넘버 sub(n, n, 17)을 갖는 수식은 증명될 수 없다'는 수식 G를 구성했는데, 소인수분해의 유일성에 의해 G가 가리키는 수식이 바로 G 자신임이 드러난다. G는 스스로에 대해 '나는 증명될 수 없다'고 말한다. 만약 G가 증명된다면 이는 '증명이 존재하지 않는다'는 G의 주장과 정면으로 모순되므로, 일관된 체계에서 G의 참·거짓은 결정 불가능하다. 그러나 G가 말하는 내용은 실제로 참이다. 참이면서도 그 체계 안에서 결정할 수 없는 명제가 존재하니, 그 체계는 불완전하다. 새 공리를 덧붙여 G를 증명하려 해도, 같은 방식으로 새로운 참인 미결정 명제 G′가 다시 만들어진다. 자기 꼬리는 결코 잡을 수 없다.
실무자에게 남는 함의
두 번째 정리, 즉 어떤 공리 집합도 자기 일관성을 증명할 수 없다는 결론은 첫 번째로부터 자연스럽게 따라 나온다. 만약 어떤 체계가 자신의 일관성을 증명할 수 있다면, 첫 번째 정리에 의해 그 체계는 불완전하고, '증명할 수 없는 참인 수식이 있다'는 진술은 곧 G와 같아진다. 그런데 우리는 그 체계가 G를 증명할 수 없음을 이미 안다. 따라서 자기 일관성을 증명하는 체계는 존재할 수 없다.
소프트웨어를 다루는 사람에게 이 결과는 추상적인 옛 논리학 이야기가 아니다. 정지 문제의 결정 불가능성은 '임의의 프로그램이 특정 입력에서 멈추는지'를 판정하는 완전한 알고리즘이 원리적으로 불가능하다는 뜻이며, 이는 정적 분석 도구, 검증기, 타입 시스템이 왜 근본적인 한계를 안고 근사·보수적 판정에 의존할 수밖에 없는지를 설명한다. 형식 검증이 '이 시스템은 절대 오류를 내지 않는다'를 스스로 완결적으로 보증하지 못하고 언제나 외부 가정과 신뢰 기반에 기대는 것도 같은 맥락이다. 동시에 유의할 점도 있다. 불완전성은 '모든 명제가 미결정'이라는 뜻이 아니라, 충분히 표현력 있는 체계라면 반드시 그런 명제가 존재한다는 것이다. 실무의 대다수 문제는 여전히 결정 가능한 영역 안에 있다. 괴델이 남긴 것은 절망이 아니라, 증명 가능성과 진리가 같지 않다는 경계선의 정확한 위치이며, 그 의미는 네이글과 뉴먼이 1958년에 적었듯 지금까지도 온전히 다 헤아려지지 않았다.