기계는 증명할 수 없는 것을 인간은 알 수 있는가?
1928년 가을, 빈 대학
쿠르트 괴델(Kurt Friedrich Gödel)은 빈 대학 도서관에서 논리학 책들과 씨름하고 있었다. 스물두 살. 마르고 수줍은 청년. 그의 앞에는 버트런드 러셀(Bertrand Arthur William Russell)과 알프레드 화이트헤드(Alfred North Whitehead)의 『수학 원리(Principia Mathematica)』가 펼쳐져 있었다. 세 권으로 된 거대한 저작. 수학의 모든 것을 논리학으로 환원하려는 시도.
괴델은 그 복잡한 기호들을 천천히 따라갔다. ∀, ∃, →, ∧, ∨...
"아름답다."
그는 중얼거렸다.
"하지만... 완전한가?"
그것이 그의 질문이었다. 이 체계가 모든 수학적 진리를 포착할 수 있는가?
괴델은 철학 전공 학생이었지만, 수학에 깊이 매료되어 있었다. 특히 수학의 기초. 무엇이 수학을 가능하게 하는가?
그는 빈 학파의 모임에 참석하기 시작했다. 모리츠 슐리크(Friedrich Albert Moritz Schlick)를 중심으로 한 철학자들의 토론 모임. 논리 실증주의자들.
그들은 경험주의자였으며, 의미는 검증 가능성에 있다고 믿었다. 하지만 괴델은 그들과 달랐다. 그는 플라톤주의자로 수학적 대상들은 실재한다고 믿었다. "우리가 발견하지 못했더라도, 그것들은 거기 있다"고 믿었다.
1929년 여름, 박사논문
괴델은 박사논문을 완성했다. 제목은 "1차 논리의 완전성에 대하여".
그는 증명했다. 1차 논리에서 타당한 모든 공식은 증명 가능하다.
이것은 놀라운 결과였다.
의미론적 진리(타당성)와 구문론적 진리(증명 가능성)가 일치한다! 하지만 괴델은 만족하지 않았다. 이것은 1차 논리에 대한 것이었다. 산술은? 집합론은? 더 강력한 체계에서도 완전성이 성립하는가?
1930년 여름, 불완전성의 발견
괴델은 다음 문제로 넘어갔다. 산술의 무모순성을 증명하는 것. 이것은 다비트 힐베르트(David Hilbert)가 제시한 거대한 프로그램의 일부였다.
힐베르트 프로그램.
힐베르트의 꿈은 이것이었다:
1. 수학을 완전히 형식화한다
2. 유한한 수단으로 그 무모순성을 증명한다
3. 모든 수학적 문제가 결정 가능함을 보인다
괴델은 산술의 무모순성을 산술 내에서 증명하려 했다. 그러기 위해서는 산술의 증명들을 산술 내에서 표현해야 했다.
"증명을 어떻게 수로 표현할 수 있을까?"
그는 생각했다.
그리고 번호 매기기 방법을 발견했다. 괴델 번호.
각 기호에 번호를 할당한다:
0 → 6
= → 5
O → 7
( → 11
) → 13
"이제 공식을 숫자 열로 바꿀 수 있습니다. 예를 들어 '0 = 0'은?"
괴델은 적었다.
"6, 5, 6이 됩니다."
"하지만 이것은 세 개의 숫자입니다. 하나의 숫자로 만들어야 합니다."
그는 소수를 사용했다. 첫 번째 소수는 2, 두 번째는 3, 세 번째는 5...
"첫 번째 숫자 6을 첫 번째 소수 2의 지수로, 두 번째 숫자 5를 두 번째 소수 3의 지수로..."
2^6 × 3^5 × 5^6
"이것을 계산하면... 243,000,000!"
하나의 거대한 숫자. 하지만 이 숫자에서 역으로 원래 공식을 완벽하게 복원할 수 있다.
243,000,000을 소인수 분해하면:
2가 6번 곱해짐 → 첫 번째 기호는 6번
3이 5번 곱해짐 → 두 번째 기호는 5번
5가 6번 곱해짐 → 세 번째 기호는 6번
다시 "0 = 0"이 나온다!
"놀랍다."
괴델은 전율했다.
"증명도 숫자다. 그러면 '증명 가능성'도 산술적 속성이다!"
그는 계속 작업했다. "x는 y의 증명이다"라는 관계를 산술 공식으로 표현했다.
그리고 문득 깨달았다.
"만약 '증명 가능하지 않다'도 산술 공식으로 표현할 수 있다면..."
그는 멈췄다. 심장이 빨리 뛰었다.
"'이 문장은 증명 가능하지 않다'를 공식으로 만들 수 있다면..."
1930년 8월 26일, 빈의 카페
괴델은 카페에서 루돌프 카르납(Rudolf Carnap)을 만났다. 빈 학파의 핵심 인물. 괴델의 스승인 한스 한(Hans Hahn) 교수와 함께 그에게 논리학을 가르친 선배.
"카르납, 제가 뭔가 발견했습니다."
괴델은 조심스럽게 말했다.
"힐베르트 프로그램에 대해..."
카르납은 커피를 내려놓았다.
"말해보게, 괴델."
"저는... 어떤 일관된 산술 체계도 완전할 수 없다는 것을 증명했습니다."
"뭐라고?"
"참이지만 증명할 수 없는 문장이 존재합니다. 항상."
괴델은 냅킨을 꺼내 설명하기 시작했다.
"제가 이런 문장을 만들었습니다.
G: '문장 G는 증명 가능하지 않다.'"
"자기 자신에 대해 말하는 문장?"
"네. 문장 G가 거짓이라고 가정하면, G가 증명 가능하다는 뜻입니다. 하지만 거짓인 문장이 증명된다면 체계가 모순입니다."
"그러면 G는 참이어야 하는군."
"맞습니다. G는 참입니다. 정말로 증명할 수 없습니다. 그런데 그게 문제입니다. 참이지만 증명할 수 없는 문장이 존재한다는 것이죠."
카르납은 놀라서 괴델을 바라보았다.
"하지만... 그렇다면 힐베르트 교수님의..."
"네. 완전하면서 무모순한 체계는 불가능합니다."
카르납은 한참 침묵했다.
"괴델, 자네는 큰일을 해냈네. 다음 주 쾨니히스베르크 회의에서 발표해야 해."
1930년 9월 7일, 쾨니히스베르크
2차 정밀과학 인식론 회의. 독일 쾨니히스베르크.
유럽의 저명한 수학자와 철학자들이 모였다. 루돌프 카르납, 아르네 헤이팅(Arne Heyting), 존 폰 노이만...
회의 첫날, 카르납은 논리주의를 발표했다. 헤이팅은 직관주의를. 존 폰 노이만(John von Neumann)은 형식주의를.
힐베르트 프로그램의 승리를 선언하는 듯했다.
마지막 날, 일반 토론 시간.
괴델은 방 뒤편에 조용히 앉아 있었다. 스물네 살. 아무도 그를 주목하지 않았다.
토론이 한창일 때, 괴델은 조용히 손을 들었다.
"제가 한 가지 결과를 발견했습니다."
그의 목소리는 작았다. 거의 들리지 않을 정도로.
"충분히 강력한 형식 체계에서는, 참이지만 증명할 수 없는 명제가 존재합니다."
잠깐의 침묵.
대부분 사람들은 무슨 말인지 이해하지 못했다. 어떤 이들은 관심도 없었다.
하지만 한 사람이 있었다. 폰 노이만. 그는 번개처럼 알아챘다. 이것이 의미하는 바를. 토론이 끝나자마자, 폰 노이만은 괴델에게 다가갔다.
"괴델, 잠깐만 얘기할 수 있겠나?"
두 사람은 복도로 나갔다.
"자네 방금 뭐라고 한 건가?"
폰 노이만의 목소리는 긴박했다.
"참이지만 증명할 수 없는 명제라니?"
괴델은 설명했다. 괴델 번호, 자기지시적 문장, 증명 가능성의 산술화.
폰 노이만은 점점 창백해졌다.
"그렇다면... 힐베르트 프로그램은..."
"네. 완전한 형식화는 불가능합니다."
폰 노이만은 창밖을 바라보았다. 쾨니히스베르크의 가을 하늘.
"자네는 지금 수학의 역사를 바꿨네."
다음날, 다비트 힐베르트가 연단에 섰다. 68세. 독일 수학의 거장. 괴팅겐 대학에서 은퇴하는 날.
그는 열정적으로 연설했다.
"수학에 풀 수 없는 문제란 없습니다!"
청중이 숙연해졌다.
"우리는 의심해서는 안 됩니다. 우리는 답을 찾을 것입니다. 우리는 알아야만 합니다!"
힐베르트는 목소리를 높였다.
"Wir müssen wissen. Wir werden wissen!"
우리는 알아야 한다. 우리는 알게 될 것이다!
청중이 일어나 박수를 쳤다. 괴델은 앉아 있었다. 박수하지 않았다.
그는 알고 있었다. 힐베르트가 틀렸다는 것을. 어제 그 자신이 증명했다. 우리가 알 수 없는 것이 있다는 것을. 하지만 괴델은 아무 말도 하지 않았다. 조용히 앉아 있었다.
쾨니히스베르크 회의 후, 폰 노이만은 계속 괴델의 증명을 생각했다. 그리고 깨달았다. 괴델의 방법으로 더 강력한 결과를 얻을 수 있다는 것을.
11월 20일, 그는 괴델에게 편지를 썼다.
"친애하는 괴델,
당신의 방법을 사용하여, 저는 놀라운 결과를 얻었습니다. 어떤 체계도 자기 자신의 무모순성을 증명할 수 없습니다! 이것은 힐베르트 프로그램에 결정타입니다. 곧 논문을 제출하겠습니다.
존경을 담아, 존 폰 노이만"
괴델은 편지를 읽고 미소 지었다. 하지만 그는 이미 알고 있었다. 2차 불완전성 정리를. 사흘 전인 11월 17일, 괴델은 이미 논문을 투고했다. 두 정리를 모두 담아서.
그는 폰 노이만에게 답장을 썼다.
"친애하는 폰 노이만 교수님,
감사합니다. 하지만 저도 이미 그 결과를 얻었습니다. 제 논문에 포함되어 있습니다.
존경을 담아, 쿠르트 괴델"
폰 노이만은 답장을 받고 놀랐다. 그리고 즉시 자신의 논문 출판을 취소했다.
괴델에게 크레딧을 양보했다.
1931년, 괴델의 논문이 출판되었다.
"수학 원리 및 관련 체계들의 형식적으로 결정 불가능한 명제들에 대하여"
제목부터 길고 복잡했다. 내용은 더 어려웠다.
하지만 결론은 명확했다:
제1 불완전성 정리: 충분히 강력한 일관된 형식 체계에는, 참이지만 증명할 수 없는 명제가 존재한다.
제2 불완전성 정리: 그러한 체계는 자신의 무모순성을 증명할 수 없다.
수학계는 충격에 빠졌다.
"불가능하다!"
어떤 이들은 반발했다.
"어디선가 오류가 있을 것이다."
하지만 증명은 완벽했다. 아무도 오류를 찾지 못했다. 천천히, 의미가 스며들었다.
라이프니츠의 꿈. 모든 진리를 기계적으로 도출하는 완전한 체계. 불가능하다.
힐베르트의 프로그램. 수학을 완전히 형식화하고 무모순성을 증명하는 것. 불가능하다.
1931년 가을, 빈의 카페
괴델은 한스 한과 카페에 앉아 있었다.
"쿠르트, 네 정리가 정말로 의미하는 바가 뭐지?"
한이 물었다.
괴델은 커피를 저으며 생각했다.
"그것은... 해석하기 나름입니다."
"어떻게?"
"어떤 사람들은 이렇게 말합니다. 인간 정신은 기계보다 우월하다고. 왜냐하면 우리는 기계가 증명할 수 없는 진리를 볼 수 있으니까."
"너는 어떻게 생각하니?"
괴델은 창밖을 바라보았다.
"저는... 확신하지 못합니다. 제 정리는 형식 체계의 한계를 보여줍니다. 하지만 인간 정신도 형식 체계일 수 있습니다. 다만 자신의 한계를 증명할 수 없는."
"그렇다면 기계가 생각할 수 있다는 건가?"
"모르겠습니다."
괴델은 솔직하게 말했다.
"하지만 한 가지는 확실합니다. 생각이 무엇이든 간에, 그것은 단순한 계산 이상입니다."
1933년, 프린스턴으로
1933년, 히틀러가 권력을 잡았다. 유럽은 어두워졌다. 괴델은 프린스턴 고등연구소에 초청되었다. 아인슈타인과 같은 건물에서 일하게 되었다.
어느 날, 두 사람은 산책을 했다. 프린스턴의 가을.
"괴델, 당신의 정리가 물리학에도 적용됩니까?"
아인슈타인이 물었다.
"아마도요."
괴델이 조심스럽게 답했다.
"만약 물리학 이론을 수학적으로 형식화한다면, 같은 한계가 있을 겁니다. 모든 것을 예측할 수 있는 완전한 이론은... 불가능할 것입니다."
아인슈타인은 파이프 담배를 피우며 생각에 잠겼다.
"흥미롭군요. 그렇다면 우주에는 영원히 신비가 남아 있다는 건가요?"
"아니요."
괴델이 고개를 저었다.
"제 정리는 '기계적으로' 증명할 수 없다는 것입니다. 하지만 인간은 직관으로, 통찰로, 다른 방법으로 진리를 볼 수 있을지도 모릅니다."
"당신은 인간이 기계보다 우월하다고 믿습니까?"
"저는... 희망하고 싶습니다."
두 사람은 계속 걸었다. 낙엽이 발밑에서 바스락거렸다.
1951년, 깁스 강연
1951년, 괴델은 미국수학회의 조사이아 월러드 깁스(Josiah Willard Gibbs) 강연에 초청되었다.
제목은 "현대 수학 발전에 비추어 본 러셀의 수학 논리".
강연에서 괴델은 조심스럽게 말했다.
"제 정리는 종종 오해됩니다. 어떤 이들은 이렇게 말합니다. 수학에는 알 수 없는 진리가 있다고. 하지만 그것은 정확하지 않습니다."
청중이 주목했다.
"제가 보여준 것은, 어떤 특정한 형식 체계도 모든 진리를 포착할 수 없다는 것입니다. 하지만 우리는 더 강력한 체계를 만들 수 있습니다. 그리고 그 체계에서 이전에 증명할 수 없었던 것을 증명할 수 있습니다."
"그렇다면 끝이 없다는 건가요?"
누군가 물었다.
"네. 끝이 없습니다. 항상 더 높은 단계가 있습니다. 수학은 열려 있습니다. 영원히."
말년의 괴델
괴델은 점점 더 은둔적이 되었다. 편집증적 경향이 심해졌다.
음식에 독이 있을 수 있다는 의심이 심해져 아내 아델레가 만든 것만 먹었다.
1977년, 아델레가 입원했다. 괴델은 먹기를 거부했다.
1978년 1월 14일, 쿠르트 괴델은 굶어서 죽었다. 71세. 사망 당시 체중 30킬로그램.
괴델의 불완전성 정리는 20세기 수학과 철학에 혁명을 일으켰다.
라이프니츠와 힐베르트가 꿈꾼 완전한 형식 체계는 불가능하다는 것이 증명되었다.
하지만 동시에 새로운 가능성이 열렸다.
앨런 튜링은 괴델의 아이디어를 계산 이론으로 발전시켰다.
클로드 섀넌은 정보 이론을 만들었다.
그리고 컴퓨터 과학자들은 물었다. 괴델의 정리가 인공지능에 무엇을 의미하는가?
기계는 증명할 수 없는 것을 인간은 알 수 있는가?
아니면 인간도 형식 체계이고, 따라서 같은 한계를 가지는가?
그 질문은 아직도 열려 있다.
2025년 10월, 서울 역삼동 AI 연구소
승종은 괴델의 논문을 다시 펼쳤다. 94년 전에 쓰인 논문.
"형식적으로 결정 불가능한 명제들..."
그는 자신의 AI 모델을 바라보았다.
이 모델은 형식 체계인가?
그렇다면 괴델의 정리가 적용되는가?
이 모델이 증명할 수 없지만 참인 명제가 있는가?
힐베르트는 말했다. "우리는 알아야 한다. 우리는 알게 될 것이다."
괴델은 증명했다. "우리는 알 수 없는 것이 있다."
하지만 그것이 끝이 아니었다.
모르는 것이 있다는 것을 아는 것.
그것이야말로 진정한 지혜의 시작이었다.
역사적 주석
쿠르트 괴델 (1906-1978): 오스트리아-미국의 논리학자이자 수학자. 1930년 불완전성 정리를 발견하여 20세기 수학의 패러다임을 바꿨습니다.
1930년 쾨니히스베르크 회의: 1930년 9월 5-7일 개최. 괴델은 마지막 날 라운드테이블 토론에서 매우 조용히 첫 번째 불완전성 정리를 발표했습니다. 대부분의 사람들은 주목하지 않았지만, 폰 노이만은 즉시 그 중요성을 파악했습니다.
힐베르트의 연설: 회의 다음날, 힐베르트는 은퇴 연설에서 "Wir müssen wissen, wir werden wissen! (우리는 알아야 한다, 우리는 알게 될 것이다!)"라고 선언했습니다. 이 말은 나중에 그의 묘비에 새겨졌습니다. 아이러니하게도 괴델은 전날 이것이 불가능함을 증명했습니다.
괴델 번호: 괴델의 핵심 기술적 혁신. 논리 기호와 공식을 자연수로 인코딩하는 방법. 이를 통해 메타수학적 명제를 산술 명제로 표현할 수 있었습니다.
제1 불완전성 정리: 페아노 산술을 포함하는 일관된 형식 체계는 완전할 수 없다. 참이지만 증명할 수 없는 명제가 존재한다.
제2 불완전성 정리: 그러한 체계는 자신의 무모순성을 증명할 수 없다.
폰 노이만의 역할: 존 폰 노이만(1903-1957)은 쾨니히스베르크에서 괴델의 발표를 듣고 즉시 중요성을 파악했습니다. 11월20일 괴델에게 편지를 보내 2차 정리를 독립적으로 증명했다고 알렸지만, 괴델이 이미 11월 17일에 투고했음을 알고 출판을 포기했습니다.
힐베르트의 반응: 힐베르트와 괴델은 평생 직접 만나지 않았습니다. 힐베르트는 괴델의 결과를 처음 들었을 때 화를 냈다고 전해지지만, 수학자로서 증명의 타당성을 부정할 수 없었습니다.
괴델의 성격: 괴델은 극도로 내성적이고 조심스러운 성격이었습니다. 말년에는 편집증적 경향이 심해져 독살을 두려워했고, 1977년 아내가 입원한 후 먹기를 거부하다가, 1978년 굶어서 사망했습니다.
철학적 의미: 괴델 본인은 플라톤주의자였습니다. 그는 자신의 정리가 인간 정신의 우월성을 증명한다고 믿었습니다. 하지만 이 해석은 논쟁적입니다.