자기 참조와 대각선

"이 문장은 거짓이다." 이 문장이 참이라면 말한 대로 거짓이고, 거짓이라면 말한 것과 반대이니 참입니다. 기원전 4세기 그리스의 철학자 에우불리데스가 냈다고 전하는 이 거짓말쟁이 역설⁠(liar paradox)⁠은 2천 년 넘게 말장난 취급을 받았습니다. 그런데 19세기 말부터 수학자들은 같은 구조가 무한의 크기를 가르고, 집합론⁠(set theory)⁠의 기초⁠(basics)⁠를 무너뜨리고, 증명과 계산의 한계를 긋는 정밀한 도구라는 것을 차례로 알게 되었습니다. 이 페이지의 이야기들은 모두 같은 표 한 장으로 그려집니다. 행과 열에 같은 것들을 늘어놓고, 대각선을 읽어 모두 뒤집는 것입니다.

표를 읽는 방법: (누르면 바뀝니다). 칸을 누르면 값이 바뀝니다. 맨 아래 빨간 줄 D는 언제나 대각선(노란 칸)을 뒤집은 것입니다.

D를 번째 줄과 비교해 봅시다.

그렇다면 D를 목록에 넣으면 어떨까요? D를 k번째 줄에 넣기 새 표 넣는 순간 대각선의 k번째 칸이 바뀌고, 새 D는 다시 그 자리에서 달라집니다. 나머지 칸이 모두 같아져도 소용없습니다. 목록을 어떻게 고쳐도 D는 한 발 앞서 빠져나갑니다.

무한의 크기. 1873년 12월 할레의 칸토어는 실수⁠(real number)⁠를 자연수⁠(natural number)⁠와 짝지을 수 없다는 증명을 데데킨트에게 편지로 보냈습니다. 1874년에 발표된 그 증명은 구간을 좁혀 가는 방식이었고, 오늘날 널리 알려진 대각선 논법⁠(diagonal argument)⁠은 1891년에 나왔습니다. 표의 행을 0과 1로 된 무한 수열, 열을 자리 번호로 두면, 뒤집은 대각선 D는 어느 행과도 적어도 한 자리에서 다릅니다. 그러니 어떤 목록도 모든 수열을 담지 못하고, 이진 전개⁠(binary expansion)⁠로 적은 실수(진법⁠(positional notation)⁠)는 셀 수 있는 집합⁠(set)⁠이 아닙니다. 같은 논문에서 칸토어는 행을 '집합 A의 원소⁠(element)⁠가 짝지어진 부분집합⁠(subset)⁠'으로 바꾸어, 어떤 집합이든 그 멱집합⁠(power set)⁠이 원래 집합보다 크다는 것을 보였습니다. 무한 위에 더 큰 무한이 끝없이 쌓입니다. 1874년 논문은 이미, 0이 아닌 정수⁠(integer)⁠ 계수 다항식⁠(polynomial)⁠의 근이 되는 대수적 수(√2처럼)가 셀 수 있는 만큼뿐이라는 것에서, 어떤 그런 다항식의 근도 아닌 초월수(π나 e 같은)가 셀 수 없이 많다는 결론을 끌어냈습니다. 무한집합을 완결된 하나의 전체로 다루는 이런 논증을 불편해한 수학자도 있었고, 베를린의 레오폴트 크로네커가 대표적입니다.

모든 것의 집합. 1901년 케임브리지의 러셀은 칸토어의 멱집합 증명을 '모든 집합의 집합'에 적용해 보다가 러셀의 역설에 이르렀습니다. 표의 행과 열에 모든 집합을 늘어놓고 칸에 'x ∈ y인가'를 적으면, 대각선은 'x ∈ x인가'이고 뒤집은 줄은 자기 자신을 원소로 갖지 않는 집합들의 모임 R입니다. R이 표의 어느 행이라면 그 행의 대각선 칸에서 모순이 납니다. 칸토어에게는 '목록에 없다'는 결론이던 것이, 모든 집합이 목록에 있어야 하는 체계에서는 모순이 된 것입니다. 1902년 6월 편지를 받은 독일의 논리학자 고틀로프 프레게는 인쇄 중이던 『산술의 기본 법칙』 2권의 부록에서 자기 체계에 이 결함이 있음을 인정했습니다. 그의 체계는 어떤 성질이든 그 성질을 가진 것들의 집합이 있다고 허락했는데, '자기 자신을 원소로 갖지 않는다'는 성질이 바로 R을 만들어 냈기 때문입니다. 집합론은 1908년 에른스트 체르멜로의 공리⁠(axiom)⁠처럼, 이미 있는 집합에서 원소를 골라내는 식으로만 새 집합을 만들게 해 규칙을 좁히는 쪽으로 다시 지어졌습니다. 러셀 자신은 대상에 층을 매겨 자기보다 낮은 층의 것만 원소로 삼게 하는 타입 이론⁠(type theory)⁠으로 이 대각선을 막았습니다.

증명의 한계. 괴팅겐의 힐베르트는 수학 전체를 형식 체계⁠(formal system)⁠, 곧 정해진 기호와 추론 규칙만으로 증명이 맞는지를 기계적으로 검사할 수 있는 체계에 담고, 그 체계에서 어떤 명제와 그 부정이 함께 증명되는 일이 없다는 것(무모순성⁠, consistency⁠)을 유한한 방법으로 증명하자고 했습니다(수학 기초론 논쟁⁠(debate on the foundations of mathematics)⁠). 1930년 9월 쾨니히스베르크 학회에서 빈의 젊은 논리학자 괴델이 불완전성 정리⁠(incompleteness theorem)⁠를 처음 알렸고, 바로 다음 날 같은 도시에서 힐베르트는 "우리는 알아야 한다. 우리는 알게 될 것이다"로 끝나는 연설을 했습니다. 괴델의 첫 열쇠는 식과 증명을 수로 바꾸는 괴델 수⁠(Gödel number)⁠였습니다. 기호마다 번호를 주고, 식의 첫째 기호 번호를 2의 지수로, 둘째 기호 번호를 3의 지수로, 셋째를 5의 지수로 삼아 곱하면 식 하나가 수 하나가 되고, 그 수를 소인수분해⁠(prime factorization)⁠하면 원래 식을 되찾을 수 있습니다. 그러면 '이 식은 증명할 수 있다' 같은 식에 관한 말이 수에 관한 말, 곧 산술의 문장이 됩니다. 이제 표의 행은 '빈자리 x가 하나 있는 식', 열은 식들의 번호가 되고, 대각선은 '식의 빈자리에 그 식 자신의 번호를 넣은 문장'입니다. 여기에 '…는 증명할 수 없다'를 씌워 뒤집으면 '나는 증명할 수 없다'고 말하는 문장 G가 나옵니다. 거짓말쟁이 역설과 같은 모양이지만 '참'을 '증명할 수 있음'으로 바꾸었기 때문에, 모순 대신 한계가 나옵니다. 체계가 G를 증명한다면, 그 증명을 검사하는 계산을 통해 'G는 증명할 수 있다'는 것도 증명하게 되어, G가 말하는 것과 정면으로 부딪힙니다. 그러니 체계에 모순이 없는 한 G는 증명되지 않고, 바로 그래서 G가 말하는 내용은 참입니다. 곧 자연수의 덧셈과 곱셈을 다룰 만큼 강하고 모순이 없는 형식 체계에는 '참이지만 그 체계 안에서는 증명할 수 없는 문장'이 있습니다.

계산의 한계. 1935년 케임브리지에서 수학자 맥스 뉴먼의 강의를 들은 튜링은 '기계적인 절차'를 튜링 기계⁠(Turing machine)⁠로 정의하고, 1936년 정지 문제를 풀 수 없음을 보였습니다. 표의 행은 프로그램, 열은 입력으로 준 프로그램의 코드, 칸은 '멈추는가'입니다. 모든 칸을 옳게 채우는 프로그램 H가 있다면, H로 대각선을 읽어 반대로 행동하는 프로그램 D를 짤 수 있습니다. 그런데 D도 프로그램이니 표의 어느 행이어야 하고, 그 행의 대각선 칸에서 모순이 납니다. 이 논증이 성립하는 것은 튜링의 또 다른 발견, 곧 프로그램도 테이프 위의 기호열이라 다른 프로그램의 입력이 될 수 있다는 보편 튜링 기계⁠(universal Turing machine)⁠ 덕분입니다. 프로그램과 데이터를 같은 메모리에 두는 저장 프로그램 컴퓨터⁠(stored-program computer)⁠는 이 생각과 맞닿아 있고, 자기 참조⁠(self-reference)⁠는 그 편리함의 뒷면입니다. 같은 무렵 프린스턴의 논리학자 알론조 처치는 함수⁠(function)⁠를 만들고 적용하는 규칙만으로 계산을 적는 람다 계산⁠(lambda calculus)⁠으로 같은 한계에 이르렀습니다(처치–튜링 논제⁠, Church–Turing thesis⁠).

가장 짧은 설명. 1906년 러셀은 옥스퍼드 보들리 도서관의 사서 G. G. 베리에게서 들었다며 역설 하나를 소개했습니다. '백 글자 안으로 정의할 수 없는 가장 작은 자연수'는 방금 백 글자가 안 되는 말로 정의되었습니다. 1960년대 중반 미국의 레이 솔로모노프, 모스크바의 콜모고로프, 미국의 그레고리 차이틴이 각자 내놓은 콜모고로프 복잡도, 곧 문자열을 출력하는 가장 짧은 프로그램의 길이 K에서 이 역설은 정리가 됩니다. K를 계산하는 프로그램이 있다면 'K가 백만보다 큰 첫 문자열을 출력하라'는 프로그램을 짤 수 있습니다. 이 프로그램은 백만보다 훨씬 짧은데 K가 백만보다 큰 문자열을 출력하니 모순이고, 따라서 K는 계산할 수 없습니다. 차이틴은 같은 논증으로, 어떤 형식 체계도 충분히 큰 L에 대해서는 'K(x) > L'인 x를 하나도 증명하지 못한다는 것을 보였습니다. 비둘기집 원리⁠(pigeonhole principle)⁠에 따르면 거의 모든 문자열이 줄어들지 않는데도, 그중 어느 하나가 줄어들지 않는다는 것은 증명할 수 없다는 뜻입니다. 불완전성의 또 다른 얼굴입니다.

자기 자신을 만드는 기계. 자기 참조가 늘 불가능을 뜻하지는 않습니다. 1938년 미국의 논리학자 스티븐 클리니가 증명한 재귀 정리⁠(recursion theorem)⁠에 따르면, 어떤 프로그램이든 자기 자신의 코드를 읽어 쓰도록 고쳐 쓸 수 있습니다. 가장 간단한 결과가 자기 소스 코드를 그대로 출력하는 프로그램으로, 1979년 더글러스 호프스태터가 『괴델, 에셔, 바흐』에서 철학자 W. V. O. 콰인⁠(quine)⁠의 이름을 따 '콰인'이라 불렀습니다. 비결은 괴델 문장과 같습니다. '다음 글을 두 번 적되 두 번째는 따옴표 안에 적어라'처럼, 명령과 그 명령의 인용을 짝지어 스스로에게 한 번 적용하는 것입니다. 1940년대 말 폰 노이만은 같은 구조로 자기 자신을 복제하는 기계를 설계했습니다. 기계는 자기 설계도를 읽어 새 기계를 짓고, 설계도 자체는 해석하지 않은 채 그대로 베껴 넣습니다. 몇 년 뒤 밝혀진 DNA의 역할, 곧 단백질을 만드는 지시로 읽히면서 동시에 그대로 복제되는 기록과 같은 모양입니다. 자기 자신을 부르는 재귀⁠(recursion)⁠ 함수, 람다 계산에서 이름 없는 함수가 스스로를 부르게 해 주는 Y 조합자⁠(Y combinator)⁠도 같은 구조입니다. 변환 F에 넣어도 그대로 나오는 것, 곧 F(x) = x인 x를 F의 고정점⁠(fixed point)⁠이라 하는데, Y 조합자는 어떤 F든 그 고정점을 만들어 줍니다.

1969년 미국의 수학자 윌리엄 로베어는 이 모든 논증이 하나의 정리의 특수한 경우임을, 여러 수학 구조를 대상과 그 사이의 화살표(사상)만으로 추상화해 다루는 범주론⁠(category theory)⁠의 언어로 보였습니다. 집합의 말로 옮기면 이렇습니다. A의 원소마다 'A에서 Y로 가는 함수'를 하나씩 짝지어 모든 함수가 빠짐없이 짝을 얻는다면, Y에서 Y로 가는 모든 변환은 고정점을 가져야 합니다. 대각선 위에서 그 변환을 적용해 만든 줄도 표의 어느 행이어야 하기 때문입니다. 참과 거짓을 맞바꾸기, 멈춤과 돎을 맞바꾸기처럼 고정점이 없는 변환이 있다면 그런 나열은 불가능합니다(칸토어, 러셀, 튜링). 거꾸로 나열이 가능하면, 예컨대 프로그램이 자기 코드를 받을 수 있으면 고정점이 반드시 생기고 그것이 콰인이나 괴델 문장입니다. 역설과 콰인은 같은 동전의 양면인 셈입니다.

대각선이 통하지 않는 곳. 대각선 논법은 강력한 만큼 조건을 잘 살펴야 합니다. 끝이 있는 0/1 문자열들의 목록에 적용하면 뒤집은 대각선은 끝없는 줄이 되어 목록에 없는 것이 당연하니 아무것도 증명하지 않습니다. 끝이 있는 문자열은 셀 수 있습니다. 계산할 수 있는 실수들의 목록에 적용하면 목록에 없는 실수가 나오지만, 그렇다고 계산 가능한 실수가 셀 수 없는 것은 아닙니다. 어떤 프로그램이 실수를 끝까지 내놓는지 판정할 수 없어서 그 목록을 만드는 절차가 없고, 그래서 D를 계산할 수 없을 뿐입니다. 결론이 '모순'인지 '목록에 없음'인지 '계산할 수 없음'인지는 표가 무엇이냐에 달려 있습니다. 사람들을 가장 놀라게 한 것은 이 논증이 수학자 자신에게 되돌아온다는 점이었습니다. 괴델의 문장은 일부러 지은 것이었지만, 1977년 제프 파리스와 레오 해링턴이 램지 이론⁠(Ramsey theory)⁠의 자연스러운 명제에서도, 자연수의 기본 성질을 적은 페아노의 공리 체계(페아노 산술⁠, Peano arithmetic⁠)로는 증명할 수 없는 참을 찾아낸 뒤로 불완전성은 논리학자의 장난감이 아니라 수학의 풍경이 되었습니다. 연속체 가설⁠(continuum hypothesis)⁠이 표준 집합론에서 증명도 반증도 되지 않는다는 것도 그 풍경의 일부입니다.

이어지는 곳. 대각선 논법이 처음 가른 것은 무한의 크기였고, 그 이야기는 무한을 다루는 법에서 이어집니다. 더 줄일 수 없는 문자열이 곧 무작위라는 콜모고로프의 정의는 무작위성으로, 식을 수로 바꾼 괴델 수는 표현 바꾸기의 가장 과감한 예로 이어집니다. 자기 자신에게 되돌아가는 구조는 재귀와 수학적 귀납법⁠(mathematical induction)⁠의 바탕이기도 합니다. 괴델이 1940년부터 머문 프린스턴 고등연구소에서는 폰 노이만이 저장 프로그램 컴퓨터를 만들었고, 튜링은 블레츨리 파크에서 암호 해독 기계를 설계한 뒤 전쟁이 끝나자 컴퓨터 설계로 돌아갔습니다. 논리의 한계를 긋던 논증이 기계를 짓는 설계도가 된 것입니다. 자기 자신을 부르는 정의가 무엇을 뜻하는지는 영역 이론⁠(domain theory)⁠이 답합니다. 재귀 정의를 방정식 f = F(f)로 보고 '아직 모름'에서 시작한 근삿값들의 상한⁠(upper bound)⁠, 곧 가장 작은 고정점을 그 뜻으로 삼으며, 함수가 자기 자신을 인자로 받는 타입⁠(type)⁠ 없는 람다 계산의 모형도 연속 함수만 모아 대각선 논법의 벽을 비켜 지었습니다.