|
Seeing is believing, but believing is more than seeing. -Incompleteness, G"odel and its application- 2002/6/19 (이 글은 2002년도 1학기 집합과 수리논리 과제물로 제출되었던 보고서입니다.) Chapter 0. Preliminaries 원래 "Seeing is believing, but believing is more than seeing."이란 말은 대수기하학을 전공하시는 분들이 종종 쓰는 말1)인 것으로 알고 있다. 그러나 나는 좀 다른 관점(=Set Theory and Mathematical Logic!!)에서 이 말을 바라보고 싶다. 오히려 비유가 아닌 더 자연스러운 의미로 말이다. 저 제목을 한 번 잘 직역(!)해보자. Seeing은 보는 것을 말한다. 우리가 명확하게 볼 수 있는 것. 즉, 이 말은 수학적으로 볼 때 "증명할 수 있는 것"을 말하는 것이다. 그렇다면 Believing은? 바로 믿을 수 있는 것. "진리"를 말하는 것이다. 자, 그러면 한 번 문장을 완성해보자 :
Seeing is believing, but believing is more than seeing. 즉, 모든 진리를 증명해낼 수는 없다는 것이다. 우리가 증명에서 사용하는 강력한 (그리고 유일한) 무기인 "연역"이 실제로 모든 진리를 증명하기에는 부족함이 많다는 것을 말해주는 것이기도 하다. 그리고 이 문장의 의미는 정확히 괴델의 불완전성 정리와 일치한다. 1) seeing=geometry, believing=algebra 즉, 기하학은 대수학으로 모두 나타낼 수 있지만, 대수학은 기하학보다 많은 수학적 의미를 갖는다. (대수기하학에서는 가환대수가 미분기하학에서의 해석학 역할을 한다.) Chapter 1. G"odel's Incompleteness Theorem 그렇다면 "도대체 괴델의 불완전성 원리가 무엇길래 그렇게 말들이 많은 겁니까?"라는 질문에 대해 어떤 대답을 할 수 있을까? 매우 고지식(!)하거나 잘난 척하려는 사람 그리고 세계적인 수리논리학자(들끼리)는 다음과 같이 말할지도 모른다 : "ω-모순 없는 귀납적인 모든 논리식의 집합 k에 대하여, 귀납적인 집합식 r이 상응하며, 그 결과 v Gen r이나 Neg (v Gen r) 그 어느 것도 Flg (k)에 속하지 않는다. (이때 v는 r의 자유변수이다.)" 전혀(!!) 알아들을 수 없는 이 이상한 정리는 "수학 원리와 그와 연관된 체계들의 형식적으로 결정불가능한 명제들에 대하여 ("Uber Formal unentscheidbare S"atze der Principia Mathematica und Verwandter Systeme, I.)"라는 괴델의 논문에 적혀 있는 불완전성 정리의 Original Version이다. 이 정리는 읽어보면 알 수 있듯이 매우 형식적이고 엄밀하다. (그리고 알아들을 수 없다.) 위 진술은 너무 어려우므로 우리가 알 수 있는 수준에서 이 정리를 새롭게 써보자 : "수론2)의 모순없는 공리체계들은 반드시 결정불가능한 명제를 포함한다." 이것이 이 정리가 우리에게 말하고자 하는 핵심이다. 괴델 이전 혹은 동시대의 많은 수학자들은 완전한(complete) 공리 체계3)를 꿈꿔왔다. 힐베르트, 러셀 등이 그 대표적인 인물들이라 할 수 있겠다. 특히 힐베르트는 제2회 국제 수학자 대회(ICM, International Congress of Mathematicians)에서 23개의 문제를 제시함과 동시에 완전한 공리체계를 만들기 위한 Hilbert Program4)을 제안하였고 여러 수학자들을 자신의 프로그램에 동참하게 하였다. 그러나 괴델이 위 정리를 증명하면서 힐베르트의 꿈은 단지 꿈으로 끝나버리고 말았다. 위의 정리는 수론을 포함하는 무모순적인 수학적 체계라면 항상 증명이 불가능한 명제가 있다는 것을 말해주기 때문이다. 또한 "증명 가능한 것들=진리"라고 생각해왔던 수학자들은 이 결과로 인해 자신의 사고체계를 바꾸어야만 했다. (아마 굴욕에 가까운 느낌이 아니었을까라고 생각한다.)
그러면 불완전성 정리를 보다 잘 이해하기 위해 한 번 다른 각도로 접근해보자.
진리 := 빵 검사를 통과하는 우리가 상상할 수 있는 모든 빵. 여기서 우리는 정말 중요한 질문을 하나 할 수 있다. "우리가 상상할 수 있는 모든 빵 각각에 대해 조리법이 존재하는가?" 1931년까지는 거의 모든 제빵사(=수학자)들은 이 질문에 긍정적인 생각을 가지고 있었다. 그러나 괴델은 참인 것과 증명가능한 것은 전혀 똑같은 것이 아니라는 것-수학계, 제빵업계만 이런 것이 아니다-을 결정적으로 보여주었다. 즉, 괴델의 정리가 본질적으로 보여준 것은 진리와 증명 사이에는 어떤 차이도 없다는 믿음을 완전히 분쇄하는 것이었다. 따라서 온 세상의 빵요리사들이 다 덤벼들어서 빵요리법 사전을 만들더라도 이 사전은 영원히 불완전성을 가지고 있을 수 밖에 없다는 것이다. 즉, 조리법을 적어 놓을 수 없는 빵들이 항상 존재한다는 것이다. 결국 우리는 모든 것을 알 수는 없다. 2) 여기서 수론은 단순하게 정수론을 얘기하는 것이 아니라 수에 대한 총체적인 이론을 말한다. 3) 무모순성이 보장되며 그 체계내에서 도출되는 모든 명제들을 증명할 수 있는 공리체계. 힐베르트는 이 체계를 완전한 일종의 진리 기계(Truth Machine)로 여겼다. 진리기계는 참, 거짓을 알고 싶은 명제를 기계에 입력하면 '참, 거짓'을 답변해주는 기계를 말한다. 4) 힐베르트는 수학의 역설이 의미론적인 내용에서 기인한다고 생각하여 본질적으로 '무의미한' 체계를 창조하여 그 안에서 수학적 진술을 논하려 하였다. 이런 무의미한 체계를 형식체계라 한다. 힐베르트 프로그램은 이러한 형식체계 중 하나인 산술체계가 완전하다는 것을 증명하려는 프로젝트였다. 그러나 이 프로그램은 결국 괴델의 정리에 의해 와해된다. Chapter 2. G"odel 그러면 이와 같은 업적을 남긴 괴델이란 사람이란 누구인가? 혹자5)는 괴델에 대해서 들어봤냐는 질문에 대해 내게 다음과 같은 답변을 해주었다 : "아, 그 굶어죽었다는 수학자?" 그렇다. 그는 분명 천재였지만 정신적인 측면에서는 그리 정상적이지 못했다. 유령, 악귀와 가상 심장병에 시달린 그는 우울증과 불안증세를 치료하기 위해 정신병원을 여러 번 들락날락하기도 했다. 그는 식성 또한 매우 까다로웠고 나이가 들면서 점점 적게 먹더니 나중에는 아내가 해주는 음식만을 먹었다. 다른 사람들이 자신에게 독을 먹이려 한다는 망상에 사로잡혀 있었던 것이다. 64세가 되었을 때 그의 몸무게는 32kg에 지나지 않았다. 6년 뒤 아내가 수술을 받기 위해 입원하자 그는 음식을 먹지 않았고 결국 71세에 '영양실조와 기아'로 사망했다. 거기다 죽어가던 만년에는 자신의 업적이 결국 이발사의 역설 따위의 것을 발견한 것에 불과하지 않은가라는 심각한 고뇌에 빠지기도 하였다. 또한 괴델 자신의 연구방향은 나이를 먹음에 따라 지나칠 정도로 형이상학과 신비주의로 흘러갔다. 다음은 수학자 폴 에르디쉬의 말이다 : "괴델과 나는 대화를 많이 나누었습니다. 그는 정말로 뛰어난 재능이 있었습니다. 그는 모든 것을 알고 있었고 심지어 자신이 연구하지 않는 것에 대해서도 훤했습니다. 그런 그가 출판한 업적은 별로 많지 않다는 것이 정말 이상합니다. 훨씬 많은 저작을 내놓을 수도 있었을 텐데 말입니다. 그의 관심이 자꾸 형이상학 쪽으로 흘러가는 것 같아서 나는 늘 그와 언쟁을 했습니다. 우리는 라이프니츠에 대해서 많이 연구했는데 그때마다 나는 괴델에게 말했습니다. '당신은 수학자가 되어서 사람들에게 연구대상이 되어야지, 당신 자신이 그처럼 열심히 라이프니츠를 연구해서는 안되네.'" 이와 같이 그는 정신적으로 불안정한 사람이었으나 실제로는 프린스턴 고등학문연구소(IAS, Institute for Advanced Study)의 성실한 교수이기도 했다. 또한 그는 자신의 일에 대해 강한 혹은 지나칠 정도의 의무감을 가지고 있었다. 다음은 그당시 IAS의 교수중 한 명이었던 딘 몽고메리의 말이다 : "그는 실제로 아주 성실한 교수단의 임원이었으며, 교수단 생활에 열심히 참여했다. 이는 몇몇 사람들이 예상한 것과는 정반대였다." 그는 또한 법칙을 존중하는 사람이기도 했다.6) 이에 대해서는 다음과 같은 일화가 있다. 1948년 초에 괴델은 미국시민권을 얻을 결심을 하고 있었다. 그래서 시민권 시험 준비를 위해 미국의 헌법을 공부하기 시작하였다. 그런데 시험 전 날, 친구인 경제학자 모르겐슈테른을 만나 미국 헌법의 논리적(!!) 결점을 발견하였고, 이 결점이 미국을 독재국가로 만들 수도 있다고 하면서 경악하였다. 실제로 다음 날 시험장에서도 인터뷰를 할 때 이 발견을 주장하려 하였고 이를 가로막는데는 아인슈타인과 모르겐슈테른, 심지어는 판사까지 동원되었다고 한다. 그는 20세기 최고의 수학적 업적을 남긴 수학자였다. 그러나 자기자신에 있어서는 자신의 정리처럼 불완전한(incomplete) 사람이었다고 밖에 할 수 없겠다. 5) 수학을 전공하는 사람일리가 없다!! 6) 수학자라면 거의 모두 이렇지 않을까? (이 때, 법칙은 당연히 무모순적인 것이어야 한다.) Chapter 3. Application (Artificial Intelligence is Impossible?) 괴델의 불완전성 정리는 실로 20세기 수리논리학의 최고 업적이라 할 수 있으며 많은 수학적인 이론(ex-복잡도 이론, 디오판투스 방정식 등)들의 밑바탕을 이루는데 많이 이용되고 있다. 특히 이 글에서는 괴델의 정리가 인공지능의 불가능성을 얘기하는데 응용된다는 것을 말해보고자 한다. 인공지능의 불가능성에 괴델의 정리를 이용한 것은은 1961년 옥스퍼드의 철학자인 존 루카스가 제기했다. 그는 괴델의 정리를 이용하여 우리 인간은 알 수 있지만 기계는 증명할 수 없는 산술적 진리가 존재하기 때문에 인간 정신의 능력은 그 어떤 기계의 능력도 초월한다는 것을 주장했다. 이와 같은 논조로 1989년 이론물리학자 로져 펜로즈는 "황제의 새 마음(The Emperor's New Mind)"라는 책에서 인간의 정신은 합리적인 사고7)를 초월할 수 있기 때문에 결코 어떤 기계에서 복사될 수 없다는 것을 주장했다. 이러한 펜로즈의 주장에서 핵심적인 요소는 인간의 정신이 알 수는 있지만 어떤 고정된 규칙의 집합-즉, 컴퓨터 프로그램-을 따랐을 때 마지막 결과로 나올 수 없는 산술의 참진술이 존재한다는 것을 보여준다. 즉, 괴델의 불완전성 정리와 정확히 일치하는 것이다. 그리고 그는 이런 일이 어떻게 발생하는지에 대해서 두뇌의 뉴런의 촉발 패턴에 영향을 주는 신비한 양자사건들(quantum evnets)을 가정하였다. 그러나 이 이론에도 문제점은 있다. 왜냐하면 괴델의 정리는 형식체계, 즉 컴퓨터 프로그램이 무모순이라는 가정을 하고 있기 때문이다. 인간의 정신이 이러한 전제를 만족시키는지는 의심스러운 면이 없지 않다. 실제로 우리는 유모순적인 행동을 했을 때의 사례들을 기억할 수 있다. 만일 체계가 논리적으로 유모순이라면 괴델의 정리를 이용하려는 그 모든 시도들은 헛된 것이다. 이렇듯 괴델의 정리와 인공지능의 가능성에 대한 논쟁은 앞으로도 계속될 것이다. 7) 여기서 합리적인 사고란 논리적 추론이라는 합리적 절차에 따라 어떤 결과에 도달하기 위해 규칙이나 알고리듬을 따르는 것이라는 의미로 사용되었다. (이기성, 신중함과는 아무 상관없다.) Chapter 4. Epilogue References John L. Casti, Werner DePauli, G"odel: A Life of Logic, Persus Publishing, 2000 (박정일 옮김, 괴델, 몸과 마음, 2002) D. R. Hofstadter, Goedel, Escher, Bach: An Eternal Golden Braid, Basic Books Inc., 1979 (박영성 옮김, 괴델, 에셔, 바흐, 까치, 1999) Paul Hoffman, THE MAN WHO LOVED ONLY NUMBERS, Hyperion, 1998 (신현용 옮김, 우리 수학자 모두는 약간 미친 겁니다., 승산, 1999) D. Redmond, Numer Theory : An Introduction, Marcel Dekker, 1996 http://www.math.snu.ac.kr/~kye/lecture/02_1_set_chap_4.pdf |