논리학

사고혁명 : Rudy Rucker 저서, 김량국 옮김, 열린책들, 2001 (원서 : Mind Tools, 1988), Page 251~333

1. 생각의 법칙

2. 삼단 논법

3. 기호 논리학

4. 논리적 공간의 탐험

5. 괴델의 정리

     (1) 수의 관점에서 본 괴델의 정리

     (2) 공간의 관점에서 본 괴델의 정리

     (3) 무한의 관점에서 본 괴델의 정리

     (4) 논리의 관점에서 본 괴델의 정리

     (5) 정보의 관점에서 본 괴델의 정리

6. 튜링 기계

7. 해결이 불가능한 문제들

8. 진실의 바다

1. 생각의 법칙

마르크스 형제의 영화에서, 치코와 지포는 어떤 지독한 곤경에 처하게 된다. 그들은 어떤 방에 갇혀 절망적으로 걸어다니고 있다. 지포는 아첨기 있는 목소리로 <우리는 ≪생각해야만≫ 해!> 라고 말하고, 치코는 물리치는 손짓으로 <아니야, 이미 시도해 봤어> 라고 말한다.

논리에 대해서도 같은 말을 할 수 있다. 표면적으로는 형식 논리학을 적용하면 모든 논쟁이 해결될 것으로 보인다. 그러나 논리학에서 알려진 법칙들이 큰 도움이 되기에는 그 수가 너무 적다.

논리학의 역사는 흔히 아리스토텔레스 사상의 지배를 받던 약 2 천 년간의 고전기, 불로부터 힐버트 (Hilbert) 에 이르는 대수학 또는 기호학의 시기, 그리고 괴델 (Gödel) 로부터 현재에 이르는 현대 또는 초수학의 시기 셋으로 나뉜다고 한다. 우리는, 이번 장의 다음 세 절에서는 논리학의 이 세 시대에 대해 논의하고, 마지막 절에서는 논리학이 현재 네 번째의 기묘한 시대로 어떻게 움직이고 있는지에 대해 생각해 볼 것이다. 먼저 여기서 나는 간단히 논리학 분야에서의 인간의 희망과 인간의 성취 사이의 격차에 대해 생각해 보려고 한다.

17 세기의 철학자 고트프리트 라이프니츠는 논리학의 위대한 몽상가 중 하나였다. 그는 <보편 언어 (characteristica universalis)> 라는 보편적인 언어와 엄밀한 추론의 과학인 <추론 계산학 (calculus ratiocinator)> 을 창조하려 했다. 라이프니츠는, 논쟁의 당사자들이 모여 앉아 연필과 종이를 꺼내 들고 <계산을 시작합시다> 라고 말하는 날이 언젠가는 올 것이라고 생각했다.

하지만 라이프니츠는 그의 원대한 계획을 얼마나 실현시켰을까? 그는 참이면서 동시에 거짓인 명제는 존재하지 않는다는 <무모순성의 원리 (the principle of noncontradiction)> 를 공식화할 수 있었고, 두 개의 대상은 정확하게 모든 성질이 동일할 때에만 같다고 말할 수 있다는 <식별 불가능성의 원리 (the principle of indiscernibles)> 를 공식화했다. 한번 이 두 원리로부터 모든 진실을 계산해 보겠는가?

1954 년에, 아일랜드의 수학자 조지 불은 라이프니츠의 계획을 좀더 완벽하게 하기 위해 공동 연구를 시도하였다. 그의 고전적인 저술인 『사고의 법칙 (The Laws of Thought)』에서, 불은 논리학을 대수학에 가까운 어떤 간단하고 기계적인 과정으로 다루려고 시도했다.

불의 저술은 낙관적으로 시작된다. <다음 논고의 의도는, 추론이 수행되는 정신 조작의 근본적인 법칙을 탐구하고, 미적분학의 기호 언어를 사용하여 이 법칙들을 표현하며, 이러한 토대 위에서 논리학의 과학을 확립한 뒤, 그 방법들을 구축하는 것이다.> 불은 그의 논리학의 기본 법칙을 기술한 뒤, 계속해서 그에게 가장 중요하게 여겨진 신의 존재에 대한 증명에 클라크 (Clarke) 와 스피노자 (Spinoza) 의 법칙들을 적용하였다. 하지만 이런 분석들은 결론에 이르지 못했고, 책의 말미에서 불은 일종의 절망에 가까운 상태에 놓이게 된다. 여기에서도, 우리가 중요하게 생각하는 문제들을 해결해 주는 데 단순한 논리학이 얼마나 무기력한지, 그리고 우리의 이해 법칙에 대한 지식이 얼마나 불충분한지를 느낄 수 있을 것이다. 마치 시간이 흘러 <황금의 여명> 의 가르침들이 환상이라는 것을 알게 되듯이 말이다.

앞으로 우리가 보게 되겠지만, 논리학의 실제 규칙들은 비참할 정도로 그 수가 적다. 정말로 중요한 것은 논리적인 결과를 이끌어 내는 초기 가정의 복잡성과 수행할 준비가 된 논리적인 증명들의 길이이다.

대부분의 컴퓨터는 <난수> 를 발생시키는 프로그램을 가지고 있다. 그러나 이 수들은 진정한 의미의 난수가 아니다. 이 수들은 쉽게 예측할 수 없을 정도로 복잡한, 숨겨진 계산에 의해 발생한다. 마찬가지로, 사람들이 무작위적으로 행동하는 것처럼 보인다는 사실이 인간의 본성이 근본적으로 비논리적이라는 것을 암시하는 것은 아니다. 단지 인간 행동의 바탕에 깔린 논리적인 과정이 간단한 예측의 대상이 되기에는 너무나 복잡할 뿐이다.

현대의 논리학 연구는, 복잡하고 오랫동안 수행되는 어떤 시스템을 빠르고 간단한 논리적인 규칙으로 모사하기 어렵다는 것을 보여 준다. 자신을 아주 논리적이라고 생각하는 사람들은 자신을 지배하는 규칙을 진정으로 이해할 수는 없다는 사실에 이따금 아주 당황해한다. 19 세기의 기호 논리학을 널리 보급시키는 데 기여했고 루이스 캐럴 (Lewis Carroll) 이란 이름으로 더 잘 알려진 신부 찰스 루트위지 도지슨 (Charles Lutwidge Dodgson 1832~1898) 은 자신의 내적인 복잡성과 논리학에 대한 꿈 사이의 부등성으로 고통받은 전형적인 예이다.

고전적인 공상 문학 작품인 『이상한 나라의 앨리스 (Alice's Adventures in Wonderland)』외에도, 캐럴은 몇 가지의 진지하고 학문적인 학술서도 저술하였다. 생을 마감할 무렵, 그는 『기호 논리학 (Symbolic Logic)』이라 불리는 두 권짜리 책을 집필하는데 전력을 다했다. 그가 살아 있는 동안에는 첫번째 권만이 출판되었다. 그리고 이 책은 아리스토텔레스를 추모하여 헌정되었다.

세상이 그의 <앨리스> 를 사랑했음에도 불구하고, 캐럴은 자신의 가장 중요한 업적으로 『기호 논리학』을 꼽았다. 이디스 올리비에 (Edith Olivier) 라는 부인은 그와 옥스퍼드에서 자주 식사를 함께 했는데, 다음과 같이 말했다. <도지슨 씨는 『이상한 나라의 앨리스』에 대해 이야기한 적이 없어요. 그가 자신의 인생에 있어서 정말로 자부심을 가졌던 것은 세 가지인데, 우리는 식사를 함께할 때마다 그것에 대해 이야기하곤 했죠. 그 세 가지는 그의 주전자와 논리학, 그리고 그의 사진들이었어요.>

이것을 고려하면서, 캐럴이 불멸의 『이상한 나라의 앨리스』를 쓴 그 해에 자신에 대해 가졌던 자아상에 대해 살펴보는 것은 흥미로운 일이 될 것이다. 이 이야기는, 캐럴이 1862 년 7 월 4 일 이나, 앨리스, 그리고 이디스라는 리델 가의 세 소녀들과 뱃놀이를 하는 동안 다소 자연스럽게 만들어졌다. 앨리스가 계속적으로 캐럴을 격려한 결과, 캐럴은 1862 년 말에 그 이야기를 쓰기 시작했고, 1863 년에 초고를 완성했다. 여기서, 『루이스 캐럴의 일기 (The Diaries of Lewis Carroll)』와 『이상한 나라의 앨리스』를 완성한 1863 년의 첫번째와 마지막의 기록들을 한번 보기로 하자.

하지만 사실 1863 년은 루이스 캐럴의 생애에 있어서 가장 풍부한 정보를 만들어 낸 해였다. 그러나 그가 이와 같이 느꼈던 이유는, 소설 『이상한 나라의 앨리스』가 너무나 복잡했던 관계로, 그것을 만들어 낸 정신적인 과정을 어떠한 간단한 방법으로도 논리적으로 분석할 수 없었기 때문이다. 캐럴은 자신의 영감의 근원을 파악할 수 없었고, 따라서 자신이 무력하고 무작위적으로 행동하고 있다고 느꼈던 것이다.

논리학에서 실제로 존재하는 도구들은 일반적으로 기대되는 것보다 적다. 논리의 법칙들은 컴퓨터에서 개별적인 스위치들을 지배하는 규칙들 (예를 들어 <두 개의 ON 신호를 AND 게이트에 입력시키면 출력은 ON 이다> 와 같은) 과 비슷하다. 컴퓨터로 하여금 어떤 흥미 있는 것을 만들어 내게 하려면, 처리할 어떤 복잡한 정보의 패턴이 주어져야 하고, 아주 오랜 시간동안 작동되는 것을 허용해야만 한다. 마찬가지로, 어떤 흥미 있는 가정으로부터 출발해서 아주 오랫동안 계산을 하지 않는다면, 하나의 형식화된 논리 시스템은 어떤 놀라운 결과도 만들어 내지 않을 것이다.

이제 앞으로 우리가 하고자 하는 바는 현재 존재하는 논리학에 대해 조금 살펴보고, 논리학이 형식 시스템을 암호화하는 데 어떻게 사용될 수 있는지를 알아본 다음, 『이상한 나라의 앨리스』와 같은 좋은 작품을 쓰는 데에는 하나의 시스템이 얼마나 풍부해야만 하는지를 측정해 보는 것이다.

2. 삼단 논법

플라톤은 논리적인 증명이라는 개념과 연관 있는 최초의 인물이다. 그이 <대화> 들은 이것 또는 저것을 증명했다고 주장하는 인물들로 가득 차 있다. 하지만 플라톤 자신이 논리적인 증명을 전적으로 믿은 것은 아니다. 그는 때때로 <궤변가> 로 알려진 인물들을 소개하기도 했는데, 이들은 언어적인 기교를 이용하여 태양 아래의 모든 것을 증명하는 데에 괴팍한 즐거움을 느끼는 사람들이었다. 잘 알려진 예가 「에우티데무스 (Euthydemus)」로 알려진 대화에 나타나 있다. 여기에서 소크라테스와 그의 친구 크테시푸스는 유티데무스와 디오니소도루스 (Dionysodorus) 로 알려진 두 명의 궤변가들과 논쟁을 하고 있다.

이런 종류의 궤변론적인 증명은, <당신의 것임> 과 <아버지임> 이라는 개별적인 성질들을 결합하는 방법에 대한 계획적인 혼동에 바탕을 두고 있다. 이 증명은 <당신의 것> 이라는 말을 이미 널리 받아들여진 적합한 방법으로 사용하지 않음으로써 문제를 일으켰다. 소크라테스가 이 점을 디오니소도루스에게 지적하려 하자, 디오니소도루스는 <당신은 재잘거리고 있고, 당신은 고대인이오> 라고 말한다.

플라톤의 대화들은 등장 인물들 중 많은 사람들이 소크라테스에게 이런 식으로 이야기한다는 것을 깨닫고 나면 더욱 가까이하기가 쉬워질 것이다. 사실 플라톤과 그의 또 다른 자아인 소크라테스는 절대로 그들이 옳다고 완전히 확신하는 법이 없는 것 같다. 문제는 사실 우리가 올바른 언어의 사용법에 대한 <모든> 규칙들의 공식화 방법을 모른다는 것이다. 인간이 개발한 형식 논리학은 아주 특별한 종류의 명제들을 바르게 사용하는 방법만을 다룬다.

요즈음에는 대부분의 대학 수학 과목이 몇 개의 논리학 강연들로 시작된다. 이 강연들은 논리학에 대해 충실히 개괄해 주는 것이 아니라 단지 논리 연결사들 (아닌, 또는, 만약, 단지) 이라고 불리는 것의 올바른 사용법만을 다룬다. 학생들은 <만약 A 가 참이고 B 가 거짓이라면, 《A 는 B 를 뜻한다》는 거짓이다> 와 같은 사실들을 배운다. 이런 주제 영역은 <명제 계산 (propositional calculus)> 이라는 전문적인 분야로 우리에게 잘 알려져 있는데, 이것은 바로 불을 비롯한 19 세기 중반의 논리학자들이 활발한 연구를 펼친 덕분이었다.

과학이 가장 간단한 개념을 연구하는 것으로부터 시작되는 경우는 드물다. 어떤 과학의 창시자는 흔히 그 분야가 제시하는 가장 어려운 문제에 대해서만 연구를 하고자 했다. (《걷는 것을 배우기 전에 기어다니는 것부터 배워라》 따위는 생각하지 마라. 나는 날고 싶다!> 따라서, 진정한 최초의 논리학자라고 할 수 있는 아리스토텔레스가, 명제 계산의 간단한 규칙들에 대해 별 관심을 기울이지 않았다는 것도 그리 놀랄 만한 일은 아닐 것이다.

참-거짓 명제들의 기초적인 조합에 대한 규칙들을 공식화하는 대신, 아리스토텔레스는 대부분의 시간을 <단자적 성질들의 계산 (the calculus of monadic properties)> 이라 불릴 수 있는 것을 연구하는 데 보냈다. 다시 말해, 그는 개별적인 대상이 가져야만 하는 성질에 대한 명제들에 관심이 있었다.

이런 성질을 가진 가장 간단한 명제들은 두 개의 개별적인 성질을 다룬다. 나는 여기에서, <모든 개는 털이 많다> 와 같은 명제를 생각하고 있는데, 조금 더 부자연스럽게 말하자면 이 명제는 <《개이다》라는 성질을 가진 모든 것은 또한 《털이 많다》라는 성질도 갖는다> 를 뜻한다. 만약 성질 S (주어) 가 <개이다> 를 나타내고 성질 P (술어) 가 <털이 많다> 를 나타낸다면, 우리의 명제는 <모든 S 는 P 이다> 라는 형태를 띠게 된다.

이제, 우리가 모든 S 에 대해 이야기하느냐 아니면 단지 몇 개의 S 에 대해서만 이야기하느냐에 따라, 그리고 우리가 P 인 것에 대해 이야기하느냐 아니면 P 가 아닌 것에 대해 이야기하느냐에 따라, 우리는 두 가지의 성질에 대한 네 가지의 명제를 얻을 수 있다.

아리스토텔레스의 훌륭한 제자들이었던 중세의 논리학자들은, 명제형의 이름으로서 A, I, E, O 를 사용했는데, 이 이름들은 라틴 어의 나는 긍정한다 (AffIrmo) 와 나는 부정한다 (nEgO) 로부터 온 것이었다.

아리스토텔레스는 이런 두 개의 명제에서 하나의 결론이 도출될 수 있도록 각 명제를 서로 연결하는 방법에 관심이 있었다. 이렇게 두 개의 전제로 하나의 결론을 이끌어 내는 증명은 <삼단 논법 (syllogism)> 이라고 불린다. 아마도 가장 잘 알려진 삼단 논법은 다음과 같은 진부한 표현일 것이다.

이런 삼단 논법을 분석할 때, 우리는 첫 두 줄을 <전제> 라고 부르고 세 번째 줄을 <결론> 이라고 부른다. 결론에서 처음으로 언급된 성질은 S (주어) 라고 불리고, 두 번째로 언급된 것은 P (술어) 라고 불린다. 하나의 유효한 삼단 논법에서는, 언제나 M (중간 항목) 이라고 불리는 세 번째 성질이 있어서, 두 개의 전제 중에서 언급된다. 위의 삼단 논법에서는, <소크라테스이다> 가 S 성질이고, <죽는다> 가 P 성질이며, <인간이다> 가 M 성질이 된다.

삼단 논법을 특징짓는 데에는 두 가지 방법이 있다. 첫번째 방법은 사용된 명제들의 종류와 관계 있다. 위의 소크라테스 삼단 논법에서는, 사용된 세 개의 명제 모두가 보편 긍정인 A 형의 명제들이다. 따라서 이 삼단 논법은 <식 (mood)> AAA 라고 한다. 다른 식으로는 EIO, AOO 등이 있다. 통틀어서 모든 식의 개수는 4 × 4 × 4, 즉 64 개이다.

AAA 식은 흔히 바바라, 즉 b A r b A r A 라고 불린다. 여기에서 <바바라> 는 소녀의 이름이 아니라, 라틴 어로 <야만인 (barbarian)> 을 뜻하는 단어의 복수형이다. 야만인조차 AAA 식으로 놓여진 간단한 삼단 논법을 만들 수 있다는 것이다.

삼단 논법을 특징짓는 두 번째의 방법은 두 개의 전제에서 성질 P, M, S 를 배열하는 것과 관계가 있다. 여기에는 <격 (figure)> 으로 알려진 가능성이 4 가지 있다.

통틀어서, 4 개의 격이 가능하고 64 개의 식이 가능하므로, 가능한 삼단 논법의 개수는 256 개이다. 이들 중 올바른 추론 양식은 19 개이다.

아래에 나열된 것들은 올바른 19 개의 삼단 논법 예이다. 이것을 읽으면서는, 비록 전제들이 맞든 틀리든 상관없이, 삼단 논법적인 추론의 법칙에 따라 <만약> 의 전제들이 유효하다면 <따라서> 의 결론도 유효하다는 것을 염두에 두기 바란다.

각 삼단 논법의 오른쪽에 있는 숫자와 글자들은 위에서 언급한 분류 체계와 관련이 있다. 각 삼단 논법의 말미에 붙은 세 개의 글자는 앞서 사용된 세 가지 명제의 형을 순서대로 나타낸 것이며, 그 삼단 논법의 <식> 을 명시한다. 또 각 삼단 논법의 말미에 붙은 숫자는 각 삼단 논법의 <격> 을 나타낸다 (주의. 사실은 유효한 삼단 논법의 형태가 5 개 더 있다. 이것은 1:AAI, 1:EAO, 2:AEO, 2:EAO, 그리고 4:AEO 이다. 이 형태들은 기본적인 19 개의 유효한 형들로부터 파생된 것이다).

기원전 322 년 아리스토텔레스가 죽은 뒤, 그의 논리학 저서들은 『논리학 (Organon)』이라는 책으로 엮어졌다. 여기에서 organon 이란 <과학의 도구> 를 의미한다. 수백만의 젊은이들이 중세 대학에서 아리스토텔레스의 논리학을 연구하였다. 좀더 유명한 교재들 중 하나로는 13 세기 전반기에 파리에서 출판된 샤이어스우드의 윌리엄 (William of Shyreswood) 의 『논리학 입문 (Introductiones in Logicam)』이 있다. 이 책의 흥미로운 특징은, 학생들이 각 격이 올바른 삼단 논법 식들을 쉽게 외울 수 있도록 말도 안 되는 기억용 시를 첨가했다는 것이다.

Barbara celarent darii ferio baralipton

Celantes dabitis fapesmo frisesomorum;

Cesare campestres festion baroco; darapti

Felapton disamis datisi bocardo ferison.

라틴 어의 모음만을 보면 첫 줄의 단어들인 <Barbara celarent darii ferio> 가 네 개의 올바른 제 1 격 삼단 논법 식들인 AAA, EAE, AII, EIO 를 암호화하고 있다는 것을 알 수 있다. 여러 가지의 제약 때문에, 나머지 줄들은 삼단 논법의 나머지 세 개의 격들과 어느 정도만 들어맞는다. 한 가지 제약은 이 시에 사용된 자음들이 기억술적인 의미를 갖는다는 데 있다. 또 다른 제약은 올바른 아리스토텔레스 삼단 논법을 구성하는 중세의 관점이 현대의 관점과는 약간 다르다는 점이다.

중세의 이 모든 광적인 사조에 익숙해지면서, 나는 「술집에서의 네 시간 (Four Hours in a Pub)」이라는 영어판 기억용 시를 만들지 않을 수 없었다. 각 줄은 두 부분으로 나누어진다. 각 줄의 첫 부분에는 글자 P, M, 그리고 S 를 배열함으로써 <격> 을 나타낸다. 각 줄의 두 번째 부분에는 일련의 3 음절 단어를 사용하여 그 격에서의 올바른 <식> 들을 나타낸다. 3 음절 이하의 단어들은 의미의 조각들을 맞추기 위해 존재하는 것뿐이다.

이 시의 주요 특징은 다음과 같다.

MP - SM    EAE EIO AII AAA

PM - SM    EAE AOO EIO AEE

표 3

MP - MS    OAO EAO IAI AAI AII EIO

PM - MS    IAI EAO EIO AEE AAI

삼단 논법의 한 가지 용도는 이것들을 서로 모아 하나의 긴 추론의 사슬로 만드는 것이다. 이런 삼단 논법의 사슬은 <연쇄 논법 (sorite)> 이라고 불리는데, 이것은 <무더기> 또는 <더미> 를 뜻하는 그리스 어로부터 유래한 것이다. 표 3 은 다섯 개의 전제를 사용하여 당신의 정신이 불멸이라는 것을 증명한 연쇄 논법의 예이다.

내 연쇄 논법은 삼단 논법적인 형태가 맞으므로, 아리스토텔레스의 논리학에 따라, 만약 전제들의 모두 참이라면, 결론도 또한 참이 되어야만 한다. 물론, 당신이 이 전제들 중 어떤 것을 거부한다면, 내 결론을 받아들이라고 강요당하지 않을 것이다.

3. 기호 논리학

아리스토텔레스의 삼단 논법적인 추론 방법이 올바른 것은 분명 사실이지만, 많은 사상가들은 논리학이 아리스토텔레스의 간단한 진실들 너머로 발전할 수 있어야 한다고 생각했다. 이미 2 세기에 의사 갈렌 (Galen) 은, 쌍들의 관계를 다루는 명제들에 대해서는 순수한 삼단 논법이 적합하지 않다는 것을 지적하였다. 갈렌이 든 두 가지의 예는 다음과 같다.

많은 사상가들은 삼단 논법에 의해 논의되는 성질들은 그 종류가 너무나 제한적이라고 생각하게 되었다. 그래서 아리스토텔레스가 간과한 또 다른 올바른 추론의 방법들이 있을 것이라는 의심이 생겨났다. 대수학의 기호와 방정식을 사용하는 것이 수학을 지배하게 되자, 사람들은 인간의 추론에 대해 새로운 힘과 단순함을 제공할 <논리의 대수학> 을 꿈꾸기 시작했다.

논리학을 이해하기 위한 최후의 거대한 노력이 20 세기로의 전환기에 일어났다. 논리학자들은 아리스토텔레스의 가르침을 반복하는 대신, 주제 전체에 대한 새로운 점검을 시작하였다. 이 시기에 활동한 논리학의 탐험자들 중 가장 잘 알려진 사람들로는 다음과 같은 사람들이 있다 (주요 저서와 그 시기도 같이 표시하였다).

기본적으로, 불은 논리 연결사 <또는>, <그리고>, <아닌> 에 대하여 연구하였고, 프레게는 <내포> 와 <모든> 에 관심을 가졌다. 페아노는 하나의 탄력적인 기호 체계 (flexible symbolism) 를 소개하였고, 러셀은 수학의 모든 것을 어떻게 하나의 표준적이고 논리적인 표현 양식으로 나타낼 수 있는가를 보여 주었다. 또한 힐버트는 다양한 종류의 많은 논리 시스템들을 어떻게 만드는지 보여 주었다. 이들은 이미 알려진 자명한 진실들을 핵심으로 하여 눈부신 광채가 뿜어 나오도록 했다. 비유를 바꾸면, 이들은 진실의 씨앗이 발아하도록 했으며, 빛나는 프랙탈적인 포도 덩굴이 멀리 그리고 넓게 퍼지도록 했다.

불은 대수학의 관점에서 논리학을 생각하였다. 그는 어떤 명제가 참이면 1 의 값을 갖고 거짓이면 0 의 값을 갖는 것으로 간주하였다. 그는 자신의 진리값들의 산수를 위하여 (1 + 1) 이 1 과 같다는 특별한 가정을 세웠다. 이것은 0 이 아무것도 아니고 1 은 모든 것이라는 불의 견해에 비추어 볼 때 정당화된다. 대수학과의 유비를 유지하면서, 불은 <A 그리고 B> 를 <A 곱하기 B> 와 같은 것으로 생각했고 <A - 아닌> 을 1 - A 와 같은 것으로 생각하였다.

불의 방식으로 사물을 보면 다양한 형이상학적 원리들은 대수학적인 진실이 된다. 참이면서 거짓인 명제는 없다는 라이프니츠의 무모순성 원리를 생각해 보자. 이 원리를 다르게 표현하면, <(A 그리고 A-아닌) 은 거짓이다> 가 된다. 불은 이 원리를 대수적인 방식으로 좀더 간단한 명제에서 유도해 냈다.

우선, 그는 A = A² 이라는 가정을 <사고의 근본적인 법칙> 으로 채택한다. 그러고는 다음과 같이 논증한다.

A = A²

A - A² = 0

A × (1 - A) = 0

(A 그리고 A-아닌) 은 거짓이다.

논리학을 좀더 대수학과 비슷하게 보이도록 함으로써, 불은 논리학에 대수학이 누리는 엄밀함과 필연성을 부여할 수 있기 바랐다. 그러나, 프레게와 러셀이 나중에 증명하였듯이, 대수학은 사실 어느 정도의 논리학을 전제로 하고 있으므로, 대수학에 대해 이야기하기 <전에> 먼저 논리학을 정립하는 것이 더 좋다. 불의 접근 방식에 존재하는 또 다른 문제는, 그가 논리학을 대수학과 너무 유사하게 만들려고 했기 때문에, 논리학적인 표기가 읽기 어려워졌다는 것이다. 페아노는 모든 논리적 명제를 일곱 개의 기본 기호로 공식화함으로써 논리학이 좀더 멋있게 보이도록 하였다.

표기되어 있듯이, 이 논리 기호들의 처음 다섯 가지는 <연결사> 라고 불리고, 마지막 두 개는 <양화사> 라고 불린다. 이 일곱 개의 기본 논리 기호들을 사용하는 명제들을 다루는 것을 <술어 계산 (predicate calculus)> 이라고 한다. 아리스토텔레스 논리학은 술어 계산의 일부이다. 우리는 네 가지 종류의 기본 명제들을 논리 기호 A, I, E, O 를 사용하여 적을 수 있다.

x 를 어떤 대상이라 하고, D(x) 가 <x 는 개다> 를 의미한다고 하자. 그리고 H(x) 는 <x 는 털이 많다> 를 의미한다고 하자.

훨씬 더 복잡한 종류의 명제들도 마찬가지의 논리적 형태로 쓸 수 있다. 예를 들어 x 와 y 가 수이고, L(x, y) 가 x 가 y 보다 작다는 것을 의미한다고 하자. 그러면 <가장 큰 수는 없다> 라는 명제는 <모든 수 x 에 대해서, x 가 y 보다 작게 되는 y 가 존재한다> 라고 다시 쓸 수 있다. 이것의 기호 형태는 (∀x) (∃y) [L(x, y)] 이다.

술어 계산의 영역은 아주 풍부하고 복잡하다. 그러나 우리는 이 술어 계산의 영역 중 양화사를 쓰지 않고 연결사만을 사용하는 명제들의 영역만을 살펴볼 것이다. 이런 종류의 더 간단한 명제들에 대한 연구는 <명제 계산> 이라 불린다. 명제 계산은 술어 계산의 한 기본 영역으로, 아주 잘 정리되어 있다.

명제 계산에 사용되는 기호들의 표준적 의미는 그림 111 과 같은 진리치표로 가장 잘 나타낼 수 있다. 이 진리치표를 이해하기 위해 A 와 B 를 각각 명백히 참이거나 거짓인 두 개의 명제로 가정하자. 통틀어서 두 개의 명제로부터 참과 거짓의 네 가지 조합이 가능하다는 것은 어렵지 않게 생각할 수 있다. 진리치표를 참조하면, 명제 계산의 결과 (~A) 는 A 가 거짓일 때에만 참이 된다는 것을 알 수 있다. 논리적 <or> 는 포함의 의미를 가지고 있다. 다시 말해, (A V B) 는 A 가 참이거나, B 가 참이거나, 또는 A 와 B 모두가 참일 때에 참이 된다. 한편 (A & B) 는 오직 A 와 B 가 모두 참일 때에만 참이 된다. (A → B) 의 명제는 A 만큼 B 가 참이면 언제나 참이 된다. 다시 말해, (A → B) 는 A 가 참이고 B 가 거짓인 경우에만 거짓이 된다. 마지막으로, (A ↔ B) 는 A 와 B 모두가 참이거나 A 와 B 모두가 거짓인 경우에만 참이 된다.

기호는 다음 두 가지로 읽을 수 있다. A → B 는 <A 는 B 를 뜻한다>, 또는 <만약 A 이면 B 이다> 라고 읽는다. <A ↔ B> 는 <A 만약 그리고 오직 만약 B>, 또는 <A 는 논리적으로 B 와 동치이다> 라고 읽는다.

형식 논리학의 결점 중 하나는 함의 (implication) 의 기호가 인과 관계에 대한 어떤 종류의 개념도 포함하고 있지 않다는 것이다. (A → B) 는 실제로 (~A V B) 와 같은 것을 의미할 뿐이다. 따라서 논리학에 따르면, <만약 눈이 검다면, 나는 날 수 있다> 와 같은 바보 명제도 진실일 수 있다. 불행하게도, 지금까지의 함의에 대한 간단한 정의로 여기에 주어진 것보다 더 좋은 것을 제안한 사람은 없었다. 어쨌든, 함의의 기본적인 논리적 개념은 많은 종류의 논리적인 분석에 아주 효과적이었다.

구성 성분이 되는 명제들의 참과 거짓에 관계없이 언제나 참이 되는 논리적인 명제들의 조합은 <항진식 (tautology)> 이라고 알려져 있다. 일반적으로 항진식의 여부는 진리치표를 사용하여 간단하고도 기계적으로 결정할 수 있다. 여기에 몇 가지의 잘 알려진 항진식 (모든 명제 A, B, C 에 대하여 항상 참이라고 알려진 합성 명제) 들을 제시해 보도록 하겠다. 모든 항진식은 진리치표를 만들어 그것이 언제나 참이라는 것을 확인할 수 있다.

이제 일상 용어를 사용하여 이 기본 항진식들의 한 예를 들어 보기로 하자.

그림 111  명제 연결사들의 진리치표

그림 112  대우의 법칙 (the Law of Contraposition) 의 진리치표를 이용한 증명

무모순성의 법칙    당신은 행복한 동시에 슬플 수 없다.

배중 법칙            당신은 논리학을 믿거나 믿지 않을 수 있다.

이중 부정의 법칙   만약 당신이 아무것도 가지고  있지 않는게 아니라면, 당신은 무언가를 가지고 있는 것이다.

드모르간의 법칙    만약 어떤 명제가 참도 아니고 거짓도 아니라면, 그 명제는 참인 동시에 거짓이다. 만약 모든 사람이 남자도 아니고 여자도 아니라면, 모든 사람은 남자인 동시에 여자이다.

대우의 법칙          만약 청결함이 신앙심 깊음으로 이어진다면, 악마 같음은 불결함으로 이어진다.

부정 논법             만약 세계가 논리적이라면, 세계는 이치에 닿을 것이다. 그러나 세계가 이치에 닿지 않는다면, 세계는 비논리적일 것이다.

놀라운 결과          우리가 사색을 해서는 안 된다 할지라도, 우리는 왜 안 되는지를 설명하기 위해 사색해야만 한다. 따라서 어떤 경우에도 우리는 사색을 해야만 한다.

귀류법                 만약 세계가 존재하지 않았다면, 이 명제 또한 존재하지 않았을 것이다. 그러나 분명히 이 명제는 존재한다. 따라서 세계는 존재한다.

이 증명들에서 한 가지의 놀라운 점은, 이들 모두가 전적으로 참이거나 사리에 맞는 것으로 보이지는 않는다는 것이다. 즉 이것은 기본적으로 우리의 언어가 A, B, C 와 같은 철저한 참-거짓 명제들에 바탕을 둔 것이 아니라는 것이다. 하지만 우리는 우리의 현실이 무모순성의 원리와 같이 논리적인 원칙들을 따르는, 어떤 내재적인 <원자론적> 성질에 바탕을 두기 바랄 것이다.

어쨌든, 일단 항진식의 개념이 정확해지면, 우리는 <논리적인 결론> 의 개념을 공식화할 수 있다. 명제 Z 는 공식 ((A & B & C …… & X & Y) → Z 가 항진식일 때 명제 A, B, C, ……, X, Y 의 논리적인 결론이다. Z 가 A 에서 Y 까지의 명제들의 논리적인 결과라는 것은 만약 A 에서 Y 까지가 참이라면 Z 도 참이 되어야 한다는 것을 뜻한다.

믿기로 결정한 어떤 명제를 보통 <공리 (axiom)> 라고 한다. 만약 당신이 좋아하는 공리들을 모아 하나의 모음을 만들면, 이것은 하나의 <이론> 을 형성할 것이다. 만약 T 가 이런 공리적인 명제들의 모임이고, 명제 Z 가 T 속의 어떤 명제들로부터 도출되는 논리적 결론이 될 때, 우리는 Z 가 T 에 의해 <증명되었다> 고 말하고, Z 를 T 의 <정리> 라고 부를 것이다. 기호 논리학의 관점에서, 어떤 이론 T 는 이 이론이 증명할 수 있는 모든 다양한 명제들을 간결하게 요약한 것이다. 정보의 관점에서 보면, 한 이론으로부터 얻을 수 있는 다양한 결론들은 그 이론의 공리들을 사용하여 암호화되어 있는 것이다.

4. 논리적 공간의 탐험

나는 각 지역이 어떤 종류의 명제에 대응하는 하나의 큰 다차원적 공간을 <논리적 공간> 이라고 생각한다. 나는 어떤 명제들을 참이라고 생각한다. 이 영역들은, 말하자면 밝게 빛나고 있다. 내가 거짓이라고 알고 있는 명제들의 공간은 어둡게 되어 있고, 다른 모든 지역은 내가 그 명제들에 대해 어떻게 생각하느냐에 따라 다소 밝거나 어둡게 빛나고 있다.

공간적인 유사성을 고려하면서, 나는 내 고향 별을 명확하게 알고 있는 많은 것들로 비유할 수 있다. <나는 살아 있다>, <풀은 초록색이다>, <나의 아내는 여자이다>, <나의 개는 털이 많다>, <물은 축축하다>, <10 은 삼각수이다> 등 이 모든 것들은 내가 참이라고 알고 있는 것들이다. 나는 밝게 빛나는 많은 진실들 속에 살고 있다. 하늘 저 멀리 떠 있는 밝은 별들은 진실들의 또 다른 모임이다. 내가 뉴욕에 대해 아는 것들은 하나의 무리를 이룬다. 내가 상대성 이론에 대해 아는 것들도 하나의 무리를 이룬다. 내가 자연수의 시스템에 대해 아는 것 또한 멀리서 반짝이는 한 무리의 진실들이다.

논리학은 나로 하여금 내가 실제로 알고 있는 사실들로부터 빛나는 덩굴 손들을 뻗어 갈 수 있도록 한다. 내 친구 릭의 미술품점이 닫혀 있는 것을 보면서, 나는 그가 그토록 원했던 카리브 해로의 휴가를 떠났다는 것을 추론한다. 도로변에 쓰레기 봉투가 놓여 있는 것을 보면서 나는 쓰레기차가 오고 있다는 것을 추론한다. 이런 추론들은 간단한 삼단 논법과 비슷하다. 우리는 이것들을 우리가 깨닫고 있는 것 이상으로 자주 사용한다. 삼단 논법의 사슬인 연쇄 논법은 우리의 전 사고 과정에 걸쳐 구축되어 있다. 여기 루이스 캐럴의 『기호 논리학』에 나오는 연쇄 논법을 하나 제시한다.

진정한 <쓰레기> 를 살 수 있는 유일한 곳은 거리이다. 노래를 부름으로써 얻을 수 있는 것은 쓰레기밖에는 없다. 거리에서 파는 것들은 큰 가치가 없다. 노아의 방주에 있는 계란은 아주 가치가 있다. 노아의 방주에 있는 계란은 노래를 부름으로써 얻을 수 없다.

모든 R 은 S 이다. 모든 H 는 R 이다. 모든 S 는 V 가 아니다. 모든 E 는 V 이다. 모든 E 는 H 가 아니다.

이것은 명백한 결론을 가진 다소 간단한 연쇄 논법이다 (1:AAA, 4:AEE, 1:EAE 의 형). 그러나 우리가 피타고라스 정리의 증명이나 2 의 제곱근의 불합리성에 대한 증명과 같은 수학적인 추론들을 볼 때에는, 아주 복잡한 논리학은 주어진 증거들로부터 예측했던 것보다 훨씬 더 많은 것을 추출해낼 수 있을 것이라는 생각을 하게 된다.

라이프니츠의 꿈은, 만약 우리가 올바른 언어와 올바른 추론의 법칙을 완성할 수만 있다면, 몇 가지의 자명한 진실들로부터 출발하여 모든 진실의 불을 밝힐 수 있을 것이라는 것이었다. 그곳에 빛이 있으라!

요즈음에는 이렇게 생각하는 사람을 상상하기 힘들다. 현대는 중앙 집권적인 권위들, 즉 교회, 정부, 전통 과학, 그리고 미에 대한 개념과 같은 것들의 붕괴를 가져왔다. 20 세기 후반에 들어, 모든 진실을 거의 공짜로 얻겠다는 생각은 성배를 찾겠다는 것만큼이나 우스꽝스러운 것이다. 마우쩌둥 주석은 혁명을 신뢰하고 있을 때 다음과 같이 말했다. <천 개의 꽃을 피게 하라.> 무한히 많은 논리의 별들이 그들의 광채를 떨치게 하라!

그럼에도 불구하고 …… 세계의 모든 것에 다 이유가 있다면, 그 모든 이유가 다 이치에 합당하다면, 그리고 생명의 비밀, 성배, 그리고 철학자의 돌이 정말로 <있다면> 그건 얼마나 멋있는 일일까. 그러나, 주어진 어떤 유한한 시스템이 만들어 낼 수 있는 정보에는 복잡성과 그것의 한계를 결정하는 논리학적 정리들이 있다. 세계의 복잡성에 대해 간단한 해답을 바라는 것은 사실상 헛된 일이다.

만약 우리가 논리적인 공간을 아주 가까이에서 본다면, 자연스럽게 모든 지식이 간단한 참-거짓 명제들로부터 만들어질 수 있을 것인가 하고 호기심을 갖고 생각하게 될 것이다. 비록 <나는 행복하다> 와 같은 보통의 명제들은 다양한 정도의 진실성을 가질 수 있지만, 고차원적인 진실들은 작고 명확한 <원자적인> 진실들로부터 만들어진 것일 수도 있을 것이다. 이 절의 첫 단락에서 내가 말한, 논리적인 공간에 다양하게 그림자가 드리워진 지역들은 작고 검은 점들과 작고 흰 점들로 이루어진 것들이 아닐까.

세계를 하나의 간단한 참-거짓 명제들의 집합으로 간주하는 관점은 <논리적 원자론> 으로 알려져 있다. 논리적 원자론을 가장 우아하게 소개한 것은 루트비히 비트겐슈타인 (Ludwig Wittgenstein) 의 1912 년 작 『논리 철학 논고 (Tractatus Logico-Philosophicus)』의 첫번째 절이다.

1.        세계는 사실인 모든 것이다.

1.1      세계는 사실들의 전체이지 사물들의 전체가 아니다.

1.11    세계는 사실과, 그 사실들이 <모두> 존재하는 것임에 의해 결정된다.

1.12    왜냐하면 사실들의 전체성은 사실인 것뿐 아니라 사실이 아닌 모든 것도 결정하기 때문이다.

1.13    논리적인 공간의 사실들은 하나의 세계이다.

1.2      세계는 사실들로 나누어진다.

1.21    각 항목은 사실이거나 사실이 아닐 수 있다. 반면 다른 모든 것은 동일하게 존속된다.

비트겐슈타인은 현실에 대해 아주 명확한 그림을 마음속에 지니고 있었다. 그는 우리가 논의하고 있던 것, 즉 가능한 명제들로 채워진 가상의 공간과 같은 종류의 논리적인 공간의 관점에서 현실에 대해 말하고 있다. 궁극적으로, 세계는 사물들로 이루어진 것이라기보다는 사실들로 이루어진 것이다. 만약 참인 사실이 밝게 빛나고 다른 모든 것이 어둡다면, 논리적인 공간의 전체 패턴은 주어진 것이다. 이것이 세계이며, 이것은 논리 공간에서의 하나의 패턴이다.

어떤 사상가들은 비트겐슈타인의 명제 1.2 와 1.21 에는 이론의 여지가 있는 것으로 생각한다. 명제 1.2 는 사실들이 원자적이라는 것을 암시한다. 이 명제는 사실을 파고드는 방법이 분할이라는 인상을 준다. 다시 한번 <원자 (atom)> 라는 단어가 <베어짐이 없다> 는 뜻의 a + tom 으로부터 유래되었다는 것을 상기하자. 원자는 더 이상 나누어질 수 없는 어떤 것이다. 비트겐슈타인에게 하나의 사실은 <나는 행복하다> 라는 복잡한 명제보다 훨씬 간단한 어떤 것이다. 비트겐슈타인은 하나의 사실을 <이 원자는 저 원자의 다음에 위치한다>, 또는 <어떤 시간 t 에서, 이 입자는 공간 좌표 (x, y, z) 를 가진다> 와 비슷한 어떤 것으로 간주했을 수도 있다. 내가 아는 한, 절대로 그는 어떤 종류의 것이 하나의 근본적인 사실이 되기에 충분히 간단한 명제인지 명확한 예를 든 적이 없다. 명제 1.21 은 비트겐슈타인이 하나의 사실은 더 이상 나눌 수 없을 정도로 간단한 어떤 것을 의미한다는 의견을 확증하는 것으로 보인다. 만약 하나의 기본적인 <항목> 이 (나의 <행복> 이라는 개념과 마찬가지로) 부분들로 이루어져 있는 것이라고 할 때, 그 항목의 진실성을 바꾸면 그 부분들의 진실성도 바뀌게 된다.

비트겐슈타인에게 논리적인 공간은 컴퓨터 화면 위의 그림과 같은 것이었던 것 같다. 거기에는 최소의 <항목> 들 또는 가장 간단하고도 가능한 명제들로 이루어진 격자가 있는데, 이 점들 각각은 불이 밝혀지거나 (참) 어두울 수 (거짓) 있다. 이것은 일종의, 수에 기반을 두고 현실을 보는 방식이다.

일반적인 논의의 단계에서 거론되는 사물의 의미들은 선명하지 못하고 모호하다. 그러나 논리적 원자론은 현실이 확실한 사실들로 환원되는 어떤 심오한 수준이 있을 것이라는 희망을 버리지 않고 있다. 그러나 이 시점에서, 우리는 물질이 궁극적으로 나누어질 수 없는 어떤 입자들로 이루어진 것인가를 결정할 수 없듯이, 논리적 원자론의 정확함에 대해서도 결정할 수가 없다. 아마도 이 질문들에 대해서는 진정한 대답이란 없을 것이다.

어쨌든, 우리는 수치 해석의 영역이 간단하고 원자적인 사실들에 바탕을 두고 있다는 것을 알고 있다. 두 개의 수는 같거나 같지 않거나 둘 중의 하나이다. 여기에는 모호함의 문제란 없다. 버트란드 러셀 (Bertrand Russell) 은 앨프레드 노스 화이트헤드 (Alfred North Whitehead) 와의 공동 연구를 통해 수학의 논리적인 공간을 채우려고 지속적으로 노력했던 첫번째의 사람이었다. 러셀과 화이트헤드의 거대한 작업은 1910 년부터 1913 년까지 『수학의 원리 (Principia Mathematica)』라는 세 권짜리 책으로 마무리되었다. 『수학의 원리』는 술어 계산의 기본 법칙을 사용하여 (사실상 무로부터) 수학의 모든 것을 유도하려고 시도했다. 이런 작업이 실용적인 것은 수학자들을 단단한 논리적 기반 위에 올려 놓았기 때문이다. 이 작업이 좀더 이상적인 이유는 이것이 몇 가지의 기본 원리로부터 모든 진실을 추론하려는 라이프니츠의 계획에 일종의 연습 역할을 했기 때문이다. 『수학의 원리』는 그 목표의 달성도에 있어서 전적으로 성공적인 것은 아니었다. 그러나 이 연구는 길고 형식화된 논리적인 증명의 대단한 힘을 보여 주었다. 『수학의 원리』가 발표되고 얼마 지나지 않아, 다비트 힐버트는 러셀과 화이트헤드의 체계를 더욱 효율적으로 만들어 <형식계> 의 개념을 개발하였다.

힐버트는 아마도 위대하고 세계적인 최후의 수학자일 것이다. 한평생 그는 수학의 모든 분야 (수론, 기하학, 논리학, 고등 미적분학, 그리고 응용 수학) 에 걸쳐서 중요한 연구를 수행하였다. 그는 대부분을 괴팅겐에서 보냈으며, 그에게 끌린 수학자들과 물리학자들이 세계 각지에서 모여들었다.

힐버트는 수학이란 기본적인 전제들로부터 논리적인 결론들을 이끌어 내는 과정으로 생각할 수 있다고 믿었다. 그의 연구에 힘입어 명제 계산과 술어 계산의 모든 기본 법칙들이 알려지게 되었다. 다시 말해 이제 수학자들은 ~, V, &, →, ↔, ∀, 그리고 ∃ 의 논리적인 기호들의 의미에만 바탕을 둔 명제 구성의 올바른 규칙들을 알게 되었다.

<형식계로서의 수학> 이라는 힐버트의 생각은, (x = y), (x = 0), (z = x + y) 와 같은 모든 친숙한 수학적인 관계들은 술어 계산의 언어에서 E(x, y), Z(x), P(x, y, z) 와 같은 특별한 술어들로 간주할 수 있다는 생각에 바탕을 두고 있다. 이런 점에서, 수학의 공리들은 술어 계산의 명제들로 생각할 수 있고, 정리를 증명하는 과정은 알려진 논리학의 규칙들을 다양한 공리들에 적용하는 간단한 문제로 생각할 수 있다.

힐버트 식의 형식계는 정리를 증명하기 위한 하나의 장치로 생각할 수 있다. 그 형식계의 공리들은 그 장치의 초기 프로그램에 해당하고, 그 형식계의 논리 규칙들은 그 장치의 작동 규칙에 해당한다. 일단 프로그램이 선택되면, 그 장치는 정리들을 완전히 자동으로 증명하기 시작한다. 수학자들은 논리 공간에서 흥미로운 모든 지역들을 완전히 채울 수 있을 정도로 강력한 어떤 프로그램을 발견할 수 있기를 바라고 있다.

힐버트의 연구를 통해, 수학을 위해서는 좋은 공리들의 집합을 찾는 것이 아주 중요하다는 것이 명백해졌다. M 이라는 글자가 우리가 가지고 시작하는 기본적인 수학적 전제들의 묶음을 나타낸다고 가정해 보자. 이 묶음은 아마도, 예를 들어 사람들이 고등 학교에서 배우는 수학에 관한 모든 것 (1 + 1 = 2, x + y = y + x, 두 개의 점은 직선을 결정한다. 직각 삼각형의 네 변의 제곱은 다른 두 변의 제곱을 더한 값과 같다. 2 차 방정식의 근은 근의 공식을 이용하여 구할 수 있다. x 제곱의 도함수는 2x 이다 등) 을 포함하고 있을 것이다. 이런 접근 방법은 아주 비효율적이다. M 은 훨씬 더 작게 만들어질 수 있다. 그러나 기본적인 착상은 M 이 우리가 수학에 대해 알고 있는 모든 것을 담을 수 있을 정도로 풍부하다고 가정하는 것이며, 또한 그것으로 족하다.

힐버트는 수학에 대한 공리들의 올바른 집합은 <모순이 없어야 한다> 는 점을 지적했다. M 이 모순이 없다는 것은, 만약 우리가 M 에 포함된 공리들로부터 어떤 것들을 추론해 내기 위해 논리적인 규칙들을 사용하기 시작하면, 우리는 절대 모순에 도달해서는 안 된다는 것이다. M 은 논리 공간의 어떤 지역이 검으면서 동시에 희게 되도록 해서는 안 된다.

비록 힐버트가 곧바로 깨닫지는 못했지만, 공리들의 올바른 집합이 가져야 하는 또 하나의 성질은 <완전함> 이다. M 이 완전하다는 것은 수학에 관한 어떤 가설 H 가 주어졌을 때 M 안의 공리들을 바탕으로 H 를 증명하거나 부정할 수 있어야 한다는 것이다. M 으로부터의 결론들이 논리의 공간 속으로 퍼져 나감에 따라, 모든 지역은 각각 희거나 검은색을 명확하게 띠게 된다.

잠시 비트겐슈타인으로 돌아가면, 우리는 그가 <진실인> 모든 사실들의 묶음 F 가 모든 논리 공간 즉, 세계 전체에 대한 하나의 완전하고 모순이 없는 기술이 될 것이라고 생각했음을 알 수 있다. 물론, 전체 집합 F 는 우리가 완전히 제어하기 어려울 만큼, 그리고 상상할 수도 없을 만큼 광대할 것이다. 힐버트는 적어도 수학의 영역에 대해서만이라도 모순이 없고 완전한, 어떤 알맞은 정도로 간결한 M 이 발견될 수 있기를 희망했다.

그러나 앞으로 보게 되겠지만, 힐버트의 꿈은 실패할 운명이었다.

5. 괴델의 정리

객관적으로 보았을 때, 세계는 한 사람의 인간보다 훨씬 더 복잡하다. 그러나 우리에게는 세계를 <이해하기> 위해 세계를 어떤 간단한 방식으로 정리할 수 있는 방법을 발견하고자 하는 끈질긴 충동이 있다. 좋은 과학적 이론은 많은 수의 사실들을 몇 가지의 기본적인 법칙으로 압축하는 성질이 있다. 따라서 뉴튼의 운동에 관한 세 가지 법칙과 중력에 관한 법칙을 이용하면 앞으로 맞이할 수백 개의 일식들 날짜를 예측할 수 있다. 보어의 원자 모형이 주어지면 어떤 종류의 화합물들이 쉽게 만들어질 수 있는지를 추론할 수 있다. 수학에 대한 어떤 올바른 공리들이 주어지면 아주 다양한 수에 대한 진실들을 증명할 수 있다.

합리주의의 원대한 꿈은 언제나 <모든 것> 을 설명할 수 있는 어떤 궁극적인 이론을 찾는 것이었다. <진실> 에 대한 최후 공격을 위한 연습으로, 다비트 힐버트와 같은 논리학자들은 수학의 모든 것을 압축해서 요약할 수 있는 하나의 이론 M 을 찾기 바랐다. 여기에서 수학은 일종의 <장난감 우주> 의 역할을 한다. 만약 우리가 수학의 최종적인 이론을 어떻게 얻을 수 있는지 알 수 있다면, 우리는 현실 세계에 대한 최종적인 이론을 얻는 곳으로 한걸음 더 가까이 다가가게 될 것이다.

수학의 이상적인 이론 M 은 세 가지의 성질을 가져야만 한다. M 은 유한하게 기술될 수 있어야 하고, 모순이 없어야 하며, 완전해야 한다. M 이 <유한하게 기술될 수 있어야> 한다는 것은 <S 는 M 에 의해 증명될 수 있다> 라고 말하는 것이 무엇을 의미하는지를 명확하게 설명할 수 있도록 두꺼우면서도 유한한 책을 쓸 수 있어야만 한다는 걸 의미한다. 명제 S 에 대한 어떤 증명이 제안되면, M 의 기술을 보고 유한한 시간 내에 그 증명이 이론 M 의 규칙들에 따른 결과인지를 판정할 수 있어야만 한다.

<유한하게 기술될 수 있어야 함> 이라는 조건이 필요한 이유는, 당신이 다른 사람에게 그 이론이 무엇인가를 설명할 수 없다면, 당신은 정말로 어떤 이론을 가지고 있다고 말할 수 없기 때문이다. 이런 제한이 없다면, 우리는 단지 <수학에 대한 참인 모든 명제들의 집합을 Tr 이라고 하자> 고만 말하면 된다. Tr 의 문제점은 만약 내가 참인 모든 명제들을 나열함으로써 Tr 이 무엇인가를 말하려고 한다면, 나에게는 영원한 시간이 필요하다는 점이다. 비록 Tr 은 모순이 없고 완전하다 할지라도 Tr 은 어떤 명백한 방법으로 유한하게 기술될 수 없는 것이다. 내가 <그것이 참임으로 앞으로 인간이 증명할 수 있는 미래의 모든 수학적 명제 집합을 Hu 라고 하자> 라고 말해도 마찬가지의 문제점이 존재한다. 우리는 어떤 종류의 증명 방법이 미래에 사용될 것인지 알 수 없기 때문에, 어떤 명제 S 가 Hu 로부터 유도될 수 있는지의 여부를 어떻게 알 수 있는지 유한하게 기술할 수 없다.

어떤 이론 M 을 유한하게 기술할 수 있다는 것은, 어떤 디지털 컴퓨터를 M 이 증명할 수 있는 모든 명제들을 연속적으로 출력해 내도록 프로그래밍할 수가 있다는 것을 의미한다. 여기서의 착안점은 이 M 에 대한 유한한 프로그램을 극한에 가서는 참인 모든 명제들을 산출해 낼 수 있도록 더욱더 오랫동안 작동시킨다는 것이다. 어떤 좋은 시스템 M 을 생각해 내는 것은 인간의 할 일이고, 모든 결론들을 알아내는 것은 기계의 할 일이다. 점점 시간이 지나갈수록 다소 놀라운 결론들이 나타나기 시작할 것이며, 수행 시간 그 자체가 정보를 제공한다는 느낌이 들게 될 것이다.

좋은 이론 M 이 가져야 할 두 번째와 세 번째 성질은 무모순성과 완전성이다. 우리가 M 을 하나의 명제 출력 기계로 생각할 때 M 이 모순이 없다는 것은, M 은 어떤 명제 S 를 출력하고 난 뒤에 절대로 ~S 를 출력하지 않을 것임을 의미한다. 정리를 출력하는 기계 M 이 완전하다는 것은 어떤 주어진 명제 S 에 대해서 M 은 결국 S 나 ~S 중 하나를 출력하게 될 것이라는 것을 의미한다.

만약 어떤 이론에 모순이 있다면, 그 이론은 어떤 것들이 정말로 진실인지를 우리에게 알려 주지 않은 채로 모든 종류의 것들에 대해 증명하거나 부정하려고 할 것이다. 내가 <모든 수학적인 명제들의 모임을 Ev 라 하자> 고 말한다면, 이것은 모순이 있는 이론의 간단한 한 예가 된다. Ev 는 유한하게 기술 가능하다. 왜냐하면 나는 실제로 어떤 종류의 기호 열들이 수학적인 명제가 될 수 있는지 판정하는 규칙들의 유한 집합을 만들 수 있기 때문이다. 그리고 Ev 는 완전하다. 왜냐하면 어떠한 명제 S 에 대해서도 S 또는 ~S 가 그것으로부터 도출될 수 있기 때문이다 (사실 <모두> 가 가능하다). 그러나 Ev 는 모순이 있으며 기본적으로 가치가 없다.

만약 어떤 이론 M 이 완전하지 않다면, 그 이론이 결정할 수 없는 어떤 명제 S 가 존재할 것이다. 세계의 괴팍한 본성을 생각할 때, M 에 의해 결정이 되지 않는 명제들이 내가 정말로 호기심을 가지고 있는 명제들일 가능성은 충분히 있다. 만약 내가 <초등 학교에서 가르치는 모든 수학적 명제들을 Gr 이라 하자> 고 말한다면, Gr 은 (초등 학교 교과서를 사용하여) 유한하게 기술될 수 있고, 모순이 없다. 그러나 Gr 은 완전하지는 않다. 예를 들어, Gr 은 미적분학이나 허수와 같은 개념을 포함하는 것은 증명할 수 없다.

수학은 아주 투명하고 간단해 보인다. 논리학은 아주 강력해 보인다. 1920 년대에, 힐버트와 같은 사람들은 유한한 기술이 가능하고 모순이 없으며 완전한 어떤 수학에 대한 궁극적인 이론 M 이 있어야만 한다고 했다. 그러나 1930 년 여름, 24 살의 대학원생 쿠르트 괴델 (Kurt Gödel) 은 그런 이론은 존재하지 않는다는 것을 증명했다.

괴델의 불완전성 정리

모든 수학의 어떤 이론도,

i. 유한하게 기술이 가능하고,

ii. 모순이 없으며,

iii. 완전한 것은 없다.

이제 괴델의 정리를 수, 공간, 논리, 무한, 그리고 정보라는 다섯 가지의 다른 관점에서 살펴보기로 하자.

(1) 수의 관점에서 본 괴델의 정리

M 을 수학에 대한 모순이 없는 어떤 이론이라 하자. 그리고 M 이 유한하게 기술 가능하다고 하자. 다시 말해, M 이 사용하는 모든 공리들과 추론 규칙들을 담아 아주 두꺼운 책을 만들 수 있다고 하자. 우리가 1 장에서 논의했던 것과 같이, 이 책은 우리가 #M 이라고 부를 수 있는 어떤 특정한 정수의 이름, 즉 하나의 <L27 열> 로 생각할 수 있다.

괴델의 정리는, 실제로는 참이지만 이론 M 이 증명할 수 없는 (수 #M 에 대한) 어떤 수 명제 P(#M) 이 있다는 것을 나타낸다.

P(#M) 은 <#M 을 포함하는 이러이러한 방정식을 만족시키는 정수는 없다> 와 같은 어떤 것을 말한다. 실제로 그런 수는 <없다>. 하지만 M 은 이걸 증명할 수 없다.

다른 말로 하면, 괴델의 정리는 M 이 증명할 수 없는 자연수에 대한 어떤 실제적인 사실이 있다는 것을 나타낸다. 이것은 M 이 수학적인 우주에 대한 완전한 기술이 아니라는 것을 암시한다.

(2) 공간의 관점에서 본 괴델의 정리

다시 한번 M 을 유한한 기술을 가지는 이론, 수학에 대한 모순이 없는 어떤 이론이라고 하자. 논리적인 공간에 대한 우리의 개념으로 다시 돌아가서, 우리는 M 을 논리적인 우주에서의 일종의 씨앗이라고 생각할 수 있다. M 을 흰색으로, 그리고 논리적인 공간에서 결정되지 않은 부분들을 회색이라고 생각하자. 그리고 이제 M 이 어떤 것들은 증명하고 어떤 것들은 부정한다고 하자. M 이 증명하는 것들은 앞서 말한 씨앗으로부터 나오는 흰 가지들 위에 놓이고, M 이 부정하는 것들은 검은 가지들 위에 놓이게 된다.

괴델의 정리는 어떠한 M 을 고르더라도, 흰색이나 검은색으로 바뀌지 않는 회색의 부분이 언제나 존재하게 된다는 것을 나타낸다 (그림 113 참조). 이 정리의 증명은 M 에 대한 유한한 서술을 사용하여 언제나 회색으로 남게 되는 지역을 찾는 명령 집합을 만들 수 있다는 것을 보임으로써 이루어진다.

그림 113  괴델의 정리. <언제나 회색 지역이 존재한다.>

조금 다른 각도에서 생각할 때, 괴델의 정리는 쪽 맞추기에 대한 하나의 명제로 볼 수도 있다. 나는 (아마도 고차원적인) 어떤 공간과 증명이 가능한 개념 조각들을 가지고 있는 경우를 생각하고 있다. 이 경우, 어떤 이론은 타일들의 어떤 특정한 시작 패턴이 된다. 괴델의 정리는 우리가 어떠한 초기 패턴으로 시작해도 쪽 맞추기로 모든 공간을 메울 수는 없다는 것을 나타낸다. 어떻게 더 이상 쪽 맞추기를 할 수 없는 지역을 찾아낼 수 있는가를 알려 준다.

(3) 무한의 관점에서 본 괴델의 정리

괴델은 언젠가 과학 철학자 하오 왕 (Hao Wang) 에게, 그의 불완전성 정리는 원래 <진실> 이라는 것이 어떤 유한한 기술도 지니고 있지 않다는 깨달음으로부터 영가을 받았다고 이야기했다. 참인 모든 명제들의 집합 Tr 이 유한한 기술을 지니지 않는다는 것을 깨닫고 나자, 그는 유한하게 기술할 수 있는 어떤 M 도 Tr 의 모든 것을 요약할 수 없다는 것을 확신할 수 있었다.

괴델은 어떻게 <진실> 의 유한한 기술이 없다는 결론에 도달하게 되었을까? 그 대답은 <고대로부터 전해진 《거짓말의 역설》에 대해 생각함으로써> 이다. 아리스토텔레스조차 알고 있었던 이 역설은, <이 명제는 참이 아니다> 라고 하나의 명제 L 로 이루어져 있다. 만약 L 이 참이라면, L 은 참이 아니다. 그리고 만약 L 이 참이 아니라면, L 은 참이다. 따라서, L 은 참인 동시에 참이 아니다. 이것은 논리학의 아주 근본적인 전제인 무모순성의 법칙 (한 명제는 참인 동시에 참이 아닐 수가 <없다>) 에 위배되는 것이다. 우리는 무모순성의 원리를 포기할 수 없으므로, L 이 사실은 하나의 명제가 아님이 분명하다.

L 에는 두 가지 이상한 점이 있다. 한 가지는 이 명제가 자신을 참조하는 명제라는 것이다. L 은 <L 은 참이 아니다> 라고 말한다. L 에서 두 번째로 이상한 점은 L 은 <진실> 이라는 개념에 관해 이야기한다는 것이다. 그런데 괴델은 자기 참조가 사실 그렇게 큰 문제는 아니라는 것을 보일 수 있었다. 명제들을 L27 암호들로 봄으로써, 우리는 명제들을 특정한 종류의 수로 생각할 수 있고, 자기 참조를 나타내는 어떤 수학적인 방식을 찾을 수 있을 것이다. 만약 Q 가 명제 암호 수 (sentence code number) 들이 가지는 어떤 성질을 포함하고 있다면, <이 명제의 암호 수는 성질 Q 를 가지지 않는다> 라는 뜻의 수학적 명제를 만드는 교묘한 방법은 사실 존재하게 된다. 우리는 이 방법을 조금 뒤에 기술할 것이다.

따라서 문제가 되는 것은 L 의 두 번째 이상한 점이다. 아마도 <진실> 이라든지 <x 는 어떤 참인 명제의 암호 수이다> 라는 명제의 성질을 표현하는 유한한 수학적 방법은 없는 게 분명하다. 이것이 괴델이 <진실> 에 대해서는 어떤 유한한 수학적 기술도 존재하지 않음을 알게 된 과정이다.

우리가 무한하게 복잡한 진실이라는 개념에 대해 이야기할 수 있다는 것은, 이것을 깨닫는 순간 상당히 이상하게 느껴질 것이다. 그렇지 않다면 이것은 아주 이상한 것ㅇ 아닐 수도 있다. 우리는 <우주> 에 대해 이야기한다. 우리가 우주의 모든 것들을 요약할 수 있는 간단한 방법을 모르고 있더라도 말이다. 우주란 무엇인가? 그것은 .... <이것> 이다.

당신이 내가 <이것> 이라고 한 말의 의미를 이해할 수 있는 것은, 당신과 내가 실제로 그리고 놀랍게 비슷한 존재라는 사실에 달려 있다. <이것> 은 사실 합리적인 개념이 아니다. 이것은 개나 바위조차도 알고 있을 정도로 원초적인 것이다.

초기 논리학자들이 수학적인 사고로부터 이런 신비적인 잔여물들을 제거하기 희망했다는 것은 그리 놀라운 일이 아니다. 그들이 잘할 수 있는 것은 추론이었고, 그들은 전세계를 순수한 이성 (reason) 으로 바꾸기 원했다. 그러나 괴델은 <진실> 이라는 근본적인 논리적 개념은 합리적인 정의를 전혀 갖지 않는다는 것을 증명하였다.

진실이란 무엇인가? <이것> 이다.

(4) 논리의 관점에서 본 괴델의 정리

괴델의 불완전성 정리는 진실이 어떤 합리적인 정의를 가지지 않는다는 것을 보이는 것 이외에도 많은 일을 하였다. 이 정리의 증명은, 모순이 없고 유한하게 기술할 수 있는 어떤 이론 M 을 취하여, 참이지만 M 에 의해 증명될 수는 없는 특정한 명제 GM 을 어떻게 만들어 낼 수 있는지를 보여 준다.

GM 은 <이 명제는 이론 M 에 의해 증명이 불가능하다> 를 뜻하는 어떤 명제이다. 비록 그렇게 보이지는 않지만, GM 은 실제로 하나의 수학적인 명제이며, 위에서 논의된 수 명제 P(#M) 과 동치이다. 명제 GM 은 실제로 어떻게 만들어질까? GM 의 구성은 몇 단계를 거쳐 이루어진다.

1 단계    어떤 수학적인 기호들의 열 S 를 어떤 암호 수 #S 로 나타내도록 하는 (L27 암호와 같은) 암호화 과정을 만든다. 이것은 상당히 간단하다.

2 단계    M 은 유한하게 기술이 가능하므로, <x 는 이론 M 으로부터 증명이 가능한 어떤 명제에 대한 암호 수임> 을 나타내는 유한한 수학적 성질 Pf(x) 를 찾을 수 있다. 이것은 Pf(x) 가 <암호 x 를 사용하고 시스템 M 의 공리들로부터 도출된, 그 명제에 대한 올바른 증명을 암호화하는 어떤 긴 수가 존재한다> 와 같은 것을 의미하도록 하면 된다. 결론적으로, 만약 S 가 어떤 명제이면, Pf(#S) 는 S 가 M 으로부터 증명이 가능하다는 것을 뜻한다.

3 단계    이것은 자기 지시적인 수학적 공식을 가능하게 하는 기술적인 요령이다. 어떤 암호 수 k 로 시작하여 Sub(k) 로 불리는 또 다른 수를 우리에게 주는 어떤 사상 (map) 을 정의하자. k 가 어떤 변수 x 의 수학적인 성질을 나타내는 공식 K(x) 의 암호 수라고 가정하자. K 는 <x 는 짝수이다>, <x 는 소수이다>, 또는 <x 는 10,000 보다 크다> 등이 될 수 있다. 만약 우리가 17 과 같은 어떤 특정한 수를 x 로 집어 넣으면, 우리는 K(17) 로 씌어지는 어떤 특정한 명제를 얻게 된다. K(17) 은 <17 은 짝수이다>, 또는 <17 은 소수이다>. 아니면 <17 은 10,000 보다 크다> 가 될 수도 있다. 어찌됐든 상관없다. 우리가 k 를 k 이 암호 수라고 했던 것을 상기하자. 달리 말해 우리는 #K(x) 와 같은 수를 k 라고 했다. 이제 우리는 수 k 를 K 에 집어 넣을 수 있다. 그러면 약간 자기 지시적인 명제 K(k) 를 얻게 된다. 이 명제는 자신의 암호 수로 #K(k) 를 가지고 있다. 그리고 우리가 Sub(k) 로 부르고자 하는 것이 바로 이 수이다. 일반적으로, <만약 k 가 K(x) 의 암호 수이면, Sub(k) 는 K(k) 의 암호 수인 #K(k) 이다>.

4 단계    2 단계에서 Pf(x) 는 <x 는 이론 M 으로 증명이 가능한 어떤 명제의 암호 수가 아니다> 를 뜻하는 수학적인 공식이었다. 이제 E(x) 가 <~Pf(Sub(x))> 를 뜻한다고 하고, e 를 E(x) 의 암호 수라 하자. 마무리를 위해, GM 은 E(e) 라고 하자.

GM ↔ E(e) (GM 의 정의에 의해).

     ↔ ~Pf(Sub(e)) (E(x) 의 성질이 ~Pf(Sub(x)) 이므로).

     ↔ ~Pf(#E(e))(Sub 의 정의에 의해).

     ↔ #E(e) 는 이론 M 으로 증명이 가능한 명제의 암호 수가 아니다 (Pf 의 정의에 의해).

     ↔ #GM 은 이론 M 으로 증명이 가능한 명제의 암호 수가 아니다 (GM 의 정의에 의해).

     ↔ GM 은 이론 M 으로 증명이 불가능하다.

이 모든 것의 요점은 참이면 M 으로 증명하는 것이 불가능하고 거짓이면 M 으로 증명하는 것이 <가능> 하도록 GM 을 구축한다는 것이다. 그러나 M 은 수학의 어떤 좋은 이론이라고 가정되었으므로, 우리는 거짓인 어떤 것을 증명하기를 원하지 않는다. 따라서 GM 이 거짓이면서 증명이 가능할 가능성은 배제되므로, 따라서 GM 은 참이면서 증명이 불가능해야만 할 것이다. <이 명제는 M 에 의한 증명이 불가능하다> 는 M 이 증명할 수 없는 참인 명제이다.

만약 <x 는 어떤 참인 명제의 암호 수이다> 라는 성질을 표현하는 어떤 공식 Tr(x) 가 있다면, 우리는 동일한 4단계의 과정을 거쳐서 <이 명제는 거짓이다> 라고 말하는 어떤 명제 L 을 얻을 수 있다는 것에 주목하자. L 이 자기 모순적으로, 진실은 유한하게 표현될 수 없어야만 한다는 결론을 얻는다.

(5) 정보의 관점에서 본 괴델의 정리

IBM 의 정보 이론가 그레고리 카이틴 (Gregory Chaitin) 은 『국제 이론 물리학지 (International Journal of Theoretical Physics)』에서 그의 생각을 간결하게 요약하여 <20 파운드의 정리를 10 파운드의 이론으로 증명할 수는 없다> 고 말하였다. 이 말의 기본적인 생각은 어떤 주어진 수학 이론 M 은 한정된 양만큼의 정보 I(M) 을 포함하고 있다는 것이다. M 에 포함된 정보 I(M) 은 대략적으로 M 에 대한 간결한 기술을 하기 위해 필요한 기호의 수와 일치한다. 더 복잡한 이론은 더 많은 정보를 암호화하지만, 어떤 주어진 이론은 어떤 한정된 양의 정보만을 포함한다. 그리고 저기 어딘가에는 훨씬 더 많은 양의 정보를 암호화하는 수들이 있다. 괴델의 정리의 정보 이론적인 버전은 M 은 I(M) 보다 정보 이론적인 복잡성이 훨씬 큰 수들에 대해서는 실제로 논의할 수 없다는 것을 나타낸다. <우리의 이론은 유한하나 진실은 무한하다> 라는 핵심적인 통찰은, 이 결과에 의해 <우리가 생각할 수 있는 모든 이론 M 에서, M 이 증명할 수 있는 진실의 복잡성에는 한계가 존재한다> 라는 것이 된다. 따라서 모든 것에 대해 대답할 수 있는 어떤 이론을 찾는다는 모든 생각은 여기서 폐기된다. 이론이란 어떤 엄밀한 방법으로 그 깊이를 측정할 수 있는 유한한 인공물이다. 나는 다음 장에서 정보의 관점에서 본 괴델의 정리에 좀더 이야기하고자 한다.

괴델의 정리에는 브뤼겔 (Brueghel) 의 그림에 존재하는 것 같은 엄청난 복잡함이 있다. 이것을 보는 방법은 아주 많고도 다양하다. 1930 년대의 논리학자들은 괴델의 정리의 방법들을 사용하여 괴델의 정리와 관련된 결과들로 이루어진, 어리둥절할 정도로 다양한 결론들에 도달했다. 괴델은 J. 바클리로서 (J. Barkley Rosser) 의 도움을 받아, 자신의 정리는 자신의 무모순성을 증명할 수 있는 좋은 수학 이론이란 없다는 것을 증명한다고 주장할 수 있었다. 앨론조 처치 (Alonzo Church) 는 괴델의 정리를 사용하여, 어떤 주어진 이론으로부터 어떤 명제들이 도출되는지를 결정하는 효과적인 방법은 없다는 것을 보였다. 앨프레드 타르스키 (Alfred Tarski) 는 괴델의 증명을 사용하여 진실은 정의할 수 없음을 증명하였다. 앨런 튜링 (Alan Turing) 은 누구도 어떤 주어진 프로그램이 작동할 것인지 아닌지를 예측할 수는 없다는 것에 대한 증명을 제안하였다. 에밀 포스트 (Emil Post) 는 어떤 방식으로 괴델의 정리가 수학은 반드시 창조적이고 비기계적이어야 한다는 것을 보여 주었는지 논의했다. 스티븐 클린 (Stephen Kleene) 은 괴델의 증명을 무한의 모든 수준에 대한 이름들을 찾는 것이 불가능하다는 것과 연관시켰다.

무엇보다도, 괴델의 정리는 인간의 사고가 사람들이 믿고 있었던 것보다 더 복잡하고 덜 기계적이라는 것을 보였다. 그러나 1930 년대에 일어난 초기 흥분의 돌풀이 지나고 나서, 그 결과는 기술적인 수학 (technical mathematics) 의 일부로 굳어졌다. 괴델의 정리는 수학적 논리학이라는 조직의 개인 소유물이 되어 버렸고, 많은 학자들은 괴델의 정리가 현실 세계와 관련이 있을 것이라는 어떠한 제안에 대해서도 경멸적인 태도를 보였다. 물질적이고 기술 숭배적이던 1940 년대와 1950 년대에, 괴델의 정리의 철학적인 결과들은 거의 무시되었다. 이 정리에 대한 흥미는 옥스퍼드 대학의 철학자 J. 앤터니 루카스 (J. Anthony Lucas) 가, 괴델의 정리는 기계가 생각할 수 없다는 것을 증명한다고 주장하는, 부정확하지만 아주 중요한 논문을 쓴 1961 년부터 다시 불붙기 시작했다. 최근 발표된 더글러스 호프스태터 (Douglas Hofstadter) 의 통속 과학 작품들은 더 많은 대중에게 괴델의 정리를 인식시키는 데 많은 기여를 했다.

벅민스터 풀러 (Buckminster Fuller) 는 언젠가, 만약 어떤 생각이 정말로 중요하다면, 그것은 좀더 나은 기계를 만드는 데 쓰여질 수 있을 것이라고 말한 적이 있다. 다음의 두 절에서, 우리는 괴델의 정리 이후의 기술들이 컴퓨터에 대한 현대의 생각에 어떤 영향을 미쳤는지를 살펴보려고 한다.

6. 튜링 기계

디지털 컴퓨터는 실제로 어떤 일을 할까? 컴퓨터는 입력 장치, 기억 장치, 처리 장치, 그리고 출력 장치의 네 가지 구성 요소로 이루어져 있다. 전형적인 가정용 컴퓨터에서는, 입력 장치는 키보드와 플로피디스크이고, 기억 장치는 전자적인 온-오프 스위치로 이루어진 메모리, 처리 장치는 집적 회로이며, 출력 장치는 플로피 디스크, 화상 단말기, 그리고 프린터이다. 입력 장치로 입력된 것은 기억 장치 속에서 암호화되고, 처리 장치는 기억 장치 속에 있는 것을 변경하며, 출력 장치는 기억 장치 속의 새롭게 갱신된 내용을 표시한다.

그림 114  컴퓨터

실제의 계산은 기억 장치에 대한 처리 장치의 활동으로 이루어진다. 가정용 컴퓨터는 편평하고 벌레 정도의 크기에 많은 철사들이 다리처럼 뻗어 나온 직사각형의 처리 장치 (칩) 들을 가지고 있다. 우리는 컴퓨터를 이용한 작업을 다음과 같이 상상할 수 있다. 입력 단계. 당신은 프로그램과 자료 디스켓을 넣고, 자판에 무언가를 쳐 넣는다. 이 모든 정보는 어떤 표준적인 암호화 시스템에 따라 기억 보드상에 0 과 1 로 이루어진 하나의 패턴으로 변환된다. 계산 단계. 한 마리의 작은 벌레처럼, 처리 장치의 칩은 반복적으로 기호들을 바꾸면서 기억 보드 위를 <기어다닌다>. 출력 단계. 기억 보드상의 패턴은 당신의 디스크, 화면, 그리고 프린터용 종이 위의 표시들로 해독된다. 그러면 처리 수행했던 일은 정확하게 무엇인가?

i. 처리 장치는 그것이 보고자 하는 장소에 있는 기호를 읽을 수 있다. 다시 말해, 처리 장치는 그 스위치가 켜져 있는지 꺼져 있는지를 말할 수 있다.

ii. 처리 장치는 현재 조사 중인 기억 위치의 내용을 바꿀 수 있다. 다시 말해, 처리 장치는 관찰 중인 스위치의 상태를 바꿀 수 있다.

iii. 처리 장치는 새로운 기억 장소로 주의를 옮길 수 있다.

iv. 처리 장치는 자신의 내부 상태를 바꿀 수 있다. 다시 말해, 처리 장치는 다음에 무엇을 할 것인가에 대한 선호도를 바꿀 수 있다.

컴퓨터가 무엇을 하는가에 대한 이런 생각은 앨런 튜링 (Alan Turing) 의 1936 년도 논문 「결정 문제에의 응용을 고려한, 계산 가능한 수들에 관하여 (On Computable Numbers, with an Application to the Entscheidungsproblem)」로부터 얻어진 것이다. 계산에 대한 그의 논의는 <튜링 기계> 라고 불리는 하나의 특별하고 간단한 컴퓨터에 바탕을 두고 있다. 원칙적으로, 튜링 기계는 다른 컴퓨터들이 할 수 있는 모든 계산을 수행할 수 있다. 하지만 튜링 기계는 아주 느리게 작동하여, 사실상 아무도 그것을 만들지 않는다. 그럼에도 불구하고, 튜링 기계는 너무나 잘 알려져 있어서, 어떤 마음씨 좋은 공무원은 국회 도서관에 <튜링 기계의 마케팅> 에 대한 책 서가를 따로 마련해 놓기까지 했다!

튜링 기계는 긴 종이 테이프가 통과하는 상자와 비슷하게 생겼다 (그림 115 참조). 또한 이 상자에는, 숫자가 매겨지고 앞뒤로 움직일 수 있는 막대기가 있다. 이 막대기 위의 숫자들은 튜링 기계의 <내부 상태> 를 의미하고, 이 막대기의 길이는 컴퓨터 처리 장치의 복잡성을 나타낸다. 종이 테이프는 정사각형의 구획들로 이루어져 있고, 각 구획은 비어 있거나 </> 표시가 되어 있다. 테이프는 위에서 언급한 기억 보드의 역할을 한다. 이 기계에 입력을 주기 위해서는, 테이프의 몇몇 구획에 표시를 하고 색칠된 구획들 중 가장 왼쪽에 있는 것을 기계 판독기 안으로 집어 넣는다. 그리고 기계의 상태를 1 로 놓아 기계를 작동시킨다. 시간이 지남에 따라, 기계는 한번에 사각형 하나씩만큼 테이프를 앞뒤로 움직이며 새로운 </> 를 써넣거나 기존의 </> 를 지운다. 상태 막대는 앞뒤로 움직인다. 계산을 끝낸 기계는 움직임을 멈추고 저절로 꺼진다. 출력은 테이프에 남아 있는 </> 의 패턴이다.

그림 115  12-상태 튜링 기계

튜링 기계는 어느 방향으로 테이프를 움직일지, 어떻게 그 상태를 바꿀지, 언제 지울지, 그리고 언제 쓸지를 어떻게 결정할까? 튜링 기계는 주어진 프로그램에 따라 이런 것들을 결정한다. 튜링 기계를 위한 프로그램은 아주 간단한, 네 개의 기호로 이루어진 명령들의 유한한 목록이다. 각 명령은 다음과 같이 이루어져 있다.

a) 자연수 1, 2, 3, …… 이 수들은 어떤 명령을 처리할 때의 튜링 기계의 내부 상태를 나타낸다.

 b) B 또는 X 중 한 글자. 이 글자는 현재 읽히고 있는 구획의 상태를 기술한 것이다. B 는 공백을 의미하고 X 는 표시된 상태를 의미한다.

c) B, X, R, 또는 L 중 한 글자. 이 글자들은 기계가 취할 수 있는 행동들을 나타낸다. B 는 <이 구획의 표시를 지워라>, X 는 <이 구획에 표시를 하라>, R 은 <테이프를 한 구획 오른쪽으로 움직여라>, 그리고 L 은 <테이프를 한 구획 왼쪽으로 움직여라> 를 의미한다.

d) 자연수 0, 1, 2, 3, …… 이 수들은 명령을 수행하고 난 뒤 기계가 취할 내부 상태를 나타낸다. 상태 0 은 <꺼진> 상태이다.

전형적인 튜링 기계 명령은 1XB2, 2BR3, 3BR4, 4BX4, 4XR5 등과 같은 형태를 띤다. 4XR5 명령은 <만약 네가 단계 4 에 있다면, 그리고 네가 어떤 색칠된 구획을 읽고 있다면, 오른쪽으로 한 구획만큼 움직이고 단계 5 로 들어가라> 는 것을 뜻한다.

꺼져 있는 튜링 기계는 0 의 상태에 있는 것이고, 상태 막대를 0 에서 1 로 밀어 기계를 켜는 순간에 튜링 기계의 상태는 1 이 된다. 그때 기계는 조사 중인 구획의 내용을 검사한다. 만약 그 구획이 비어 있다면 기계는 명령 목록을 조사하여 1B 로 시작되는 명령을 찾을 것이고, 만약 그 구획이 표시되어 있다면 기계는 목록을 조사하여 1X 로 시작되는 명령을 찾을 것이다. 기계가 1XB2 명령을 찾았다고 해보자. 이 명령은, <만약 네가 1 의 상태에서 표시된 구획 위에 있다면, 그 표시를 지우고 상태 2 로 들어가라> 는 뜻이다. 기계는 이런 방식으로 작동된다.

만약 기계가 상태 0 으로 들어가라는 명령에 도달하면, 기계는 자동으로 꺼진다. 모든 기계가 0 에 이르는 명령에 도달하는 것은 아니다. 어떤 기계는 다양한 종류의 무한 행동 루프로 들어갈 수도 있다. 무한히 작동되는 튜링 기계는 전혀 이상한 게 아니다. 튜링의 정리는 영원히 작동할 기계와 결과를 계산하고 스스로 꺼지게 될 기계를 구분하는 일반적인 방법은 없다는 것을 가르쳐 준다.

모든 튜링 기계가 취할 수 있는 상태는 한정되어 있다는 것을 기억하자. 이것은 튜링 기계가 기계의 상태를 기억하기 위해 앞뒤로 움직이는 숫자가 새겨진 하나의 막대를 포함한다고 생각하는 것이 왜 유용한지, 그리고 왜 이 막대가 단지 유한한 길이를 가질 수밖에 없다고 생각하는 것이 유용한지를 설명해 준다. 일반적으로, 튜링 기계가 가질 수 있는 상태의 수가 많으면 많을수록, 그 기계의 행동은 더욱 복잡해진다.

만약 어떤 기게의 상태가 0 이 아니어서 어떤 값 K 개의 상태를 취할 수 있다면, 그 기계에 사용되는 프로그램은 최대 2K 개의 명령 (각 명령은 2K 개의 가능한 접두어, 1B--, 1X--, 2B--, 2X--, ……, KB--, KX-- 로 시작한다) 들을 포함할 수 있다. 이것은 작동 중인 기계는 1 에서 K 까지의 어떤 수를 그 상태로 취해야만 하며, 기계가 조사 중인 구획의 상태는 B 나 X 가 되어야만 한다는 사실의 결과이다. 각 <- -> 는 4 (K + 1) 가지의 방법, 즉 L, R, B, X 중 한 글자 뒤에 0 에서 K 까지의 수들 중 하나를 붙임으로써 채울 수 있다. 그 결과 K 개의 상태를 취할 수 있는 튜링 기계에는 (4(K + 1))^2K 개의 프로그램이 사용될 수 있다. 이 수는 K 값이 작아도 아주 큰 수가 된다. 왜냐하면 K 가 2 일 때에도 이 수는 이미 20000 에 가까워지기 때문이다. 그러나 튜링 기계가 취할 수 있는 상태의 수는 <유한하고>, 큰 K 값에서는 이 값이 대략 K^2K 와 같은 크기가 된다.

튜링 기계는 어떤 곳에서 사용할 수 있을까? 튜링 기계는 어떤 용도에도 사용할 수 있다. 튜링 기계에 사용되는 테이프상의 표시들은 당신이 무엇을 계산하느냐에 따라 다양하게 나타낼 수 있다. 이것은 마치 컴퓨터의 입출력 장치의 종류에 따라 컴퓨터 기억 장치 안의 온-오프 스위치 패턴이 다양한 종류의 정보를 암호화하고 있는 것과 같다. 기억 장치에 있는 비트들의 패턴은 수, 글자, 화면의 픽셀, 또는 로켓 조정 장치의 설정 등을 나타내는 것일 수 있다.

지금은 우리의 튜링 기계를 정수를 정수로 변환하는 데 사용하는 것이라고 생각하자. 논의를 좀더 쉽게 하기 위해, 1, 2, 3, 4, …… 와 같이 0 보다 큰 수만을 고려하기로 하자. 어떤 수 K 를 K 개의 연속적인 구획에 표시하는 것으로 입력을 마치고, 가장 왼쪽의 구획에 튜링 기계의 판독기를 놓은 다음 그 기계를 켠다고 가정해 보자. 만약 그 기계가 작동을 끝내면서 L 개의 연속적인 구획들이 표시된 어떤 열을 남길 경우, 우리는 그 기계가 수 K 를 입력받아 수 L 을 출력했다고 말할 것이다. 따라서 이 기계 T 는 수치 함수 T(K) = L 을 계산하는 것으로 생각할 수 있다. 간단한 수치 함수를 계산하기 위한 명령을 기술해 보자.

T(K) = K + 1 기본 개념은 테이프상의 표시에 이어서 하나의 표시를 더하고 정지하는 것이다. 이런 계산을 할 수 있는 튜링 기계 명령 집합은 다양하다. 명령 집합 [1XR1, 1BX0] 의 2-상태 기계를 생각해 보자. 첫번째 명령은 <만약 네가 상태 1 에서 표시된 구획 위에 있다면, 오른쪽으로 한 구획만큼 움직여 그곳에서 상태 1 로 머물러라> 라는 뜻이다. 두 번째 명령은 <만약 네가 상태 1 에서 빈 구획 위에 있다면, 그 구획에 표시를 하고 상태 0 으로 들어가라> 라는 뜻이다. 상태 0 으로 들어가는 것은 <네 자신을 정지시켜라> 와 같은 의미라는 것을 상기하자. 만약 당신이 어떤 기계를 어떤 표시된 구획들 열의 왼쪽 끝에 놓고 이 명령으로 그 기계를 작동시킨다면, 그 기계는 빈 구획을 만날 때까지 오른쪽으로 이동할 것이다. 빈 구획에 도달하면, 그 기계는 별도의 표시를 하나 더 만들고 멈추게 된다. 일반적으로 이 기계에 N 개의 연속적으로 표시된 구획이 제시되면, 그 기계는 얼마간 작동한 뒤 N + 1 개의 구획들을 남긴 채 정지하게 된다. 그러면 우리는 이 기계가 T(N) = N + 1 이라는 함수를 계산했다고 말한다. 마찬가지의 함수를 더 빠르게 계산하는 규칙은 [1XL1, 1BX0] 이다. 기계는 이런 명령을 받고 오른쪽 끝까지 이동하는 대신, 단지 주어진 열의 왼쪽 끝에 하나의 표시를 더한다.

T(K) = K + 3 시작 열의 오른쪽 끝에 세 개의 표시를 더하는 5-상태 기계를 기술해 보자.

T(K) = K + K 마지막 예에서 우리는 세 개의 별도 표시들을 <세기> 위해 상태 2, 3, 4 를 사용하였다. 이번 예에서는, 선택된 K 에 따라 별도의 표시들이 몇 개 만들어져야 할지 결정된다. 방법은 원래의 K 를 계수기 (counter) 로 사용하여 K 에 있는 하나의 표시마다 두 개씩 별도 표시를 하는 것이다. 좀더 정확하게 말해서 K 에 있는 표시들을 하나씩 지우면서 그 각각에 대해 두 개씩의 표시를 다시 하는 것이다. 이 계산을 위해서는 8 개의 상태가 필요하다.

T(K) 가 정의되지 않은 경우 : 어떤 튜링 기계가 답을 출력하지 않는 채로 영원히 계산하게 되는 경우는 언제나 일어날 수 있다. 여기서 어떤 루프로 들어가 어떤 출력도 하지 않게 되는 튜링 기계의 예를 하나 들어 보자. T 가 두 개의 명령 [1XL2, 2BR1] 으로 이루어져 있다고 하자. T 는 입력 K 에서 첫번째 표시를 가진 구획을 찾고, 찾은 구획의 왼쪽으로 한 구획만큼 이동한 뒤 다시 오른쪽으로 한 구획만큼 되돌아가 프로그램을 다시 수행한다. T 는 절대로 정지하지 않으므로 출력 또한 없다. 일반적으로, 어떤 주어진 프로그램이 이런 루프에 이르게 되는지 아닌지를 예측하기란 매우 어렵다.

튜링 기계는 아주 간단하지만, 모든 디지털 컴퓨터는 튜링 기계와 동치라는 것을 증명할 수 있다. 디지털 컴퓨터의 핵심은 아주 간단한 규칙에 따라 개별적인 기호들을 하나씩 바꾸는 것이다. 디지털 컴퓨터는 튜링 기계의 기본 활동인 i) 기억 공간 읽기, ii) 기억 공간에 쓰기, iii) 조사할 기억 공간의 위치를 바꾸기, iv) 처리 장치의 내부 상태를 바꾸기 외의 더 복잡한 작업은 절대 하지 않는다. 일반적으로 튜링 기계로 해결할 수 없는 문제는 어떤 디지털 컴퓨터로도 해결할 수 없다.

그림 116  K + K 튜링 기계는 두 개의 표시를 네 개의 표시로 바꾼다.

내가 기술한 튜링 기계는 사실 세 가지 종류의 입력을 받아들이는데, 그것은 바로 막대기 위에 표시된, 기계가 놓여진 상태를 표시하는 상태의 수, 명령의 4 중쌍들로 이루어진 프로그램 입력, 그리고 작업 테이프 위에 표시된 자료이다. 우리는 튜링 기계들이 모두 판독기, 참조기, 테이프 헤드, 그리고 막대 이동기로 이루어진 동일한 내부 장치를 가지고 있다고 상상할 수 있다.

판독기는 막대기의 현재 상태 (3 이라고 하자) 를 읽고 작업 테이프의 현재 구획 (표시되어 있다고 하자) 을 조사하여 다음으로 적용이 가능한 명령 (이 경우에는 3X) 의 첫 두 기호들을 알아낸다. 이 두 기호들은 참조기로 넘겨진다.

참조기는 명령 4 중쌍들을 조사하여 올바른 두 개의 기호로 시작하는 명령을 찾는다. 만약 그런 명령이 없거나 또는 그런 명령이 하나 이상 존재하면, 참조기는 상태 막대를 0 으로 움직이고 기계를 끈다. 그렇지 않다면 참조기는 판독기로부터 넘겨진, 두 개의 기호들로 시작하는 명령 (3XR4 라고 하자) 을 찾는다. 찾아진 명령의 세 번째 기호는 테이프 헤드로 넘겨지고, 네 번째의 기호는 막대 이동기로 넘겨진다.

테이프 헤드는 현재의 구획에 표시를 하거나, 현재의 구획을 지우거나, 또는 참조기로부터 넘겨진 기호 X, B, R, L 에 따라 다음의 오른쪽이나 왼쪽 구획을 볼 수 있도록 테이프를 움직인다 (만약 기호 R 이 주어지면, 테이프 헤드는 판독기가 다음 오른쪽의 구획을 볼 수 있도록 테이프를 한 구획만큼 오른쪽으로 이동시킨다).

막대 이동기는 참조기로부터 넘어온 기호와 같은 수를 가지는 명령을 판독기가 읽을 때까지 막대기를 따라 이동한다. 만약 올바른 기호를 가진 명령이 없다면, 막대 이동기는 상태 막대를 0 으로 이동시키고 기계를 끈다 (만약 찾고 있는 기호가 7 이라면, 막대는 판독기에 기호 7 을 보여 줄 때까지 이동한다).

판독기 / 참조기 / 테이프 헤드 / 막대 이동기로 구성된 일반적인 튜링 기계는 전체 상태 / 프로그램 4 중쌍 / 테이프 자료로 이루어진 어떤 혼합 입력을 받아들이는 하나의 범용 장치로 생각할 수 있다. 이 범용 기계는 유한한 개수의 명확한 작업들만 하면 되므로, 단지 어떤 한정된 개수의 개별적이고 기계적인 내부 상태들만을 지닐 것이다.

이런 기계는 <범용 튜링 기계> 라고 불린다. 범용 튜링 기계 U 는 프로그램 암호 P 와 자료 암호 D 의 두 가지 테이프 패턴을 받아들인다. U(P, D) 의 계산은, P 를 나타내는 표시들과 D 를 나타내는 표시들 사이의 공백이 있는 어떤 테이프를 U 에게 줌으로써 수행된다. U(P, D) 를 계산함에 있어서, U 는 T(K) 계산을 모사하는데, 이때 T 는 프로그램 암호 P 를 받은 기계이다.

범용 튜링 기계는 1 백 개 미만의 내부 상태를 사용하여 만들 수 있다. 그리고 만약 프로그램과 자료를 특별한 방법들로 암호화한다면, 범용 튜링 기계를 위해 필요한 상태의 수는 열 개 또는 그 이하로 줄어들 수도 있다. 열 가지의 내부 상태를 가지는 간단한 기계가 어떻게 수천 개 또는 수백만개의 상태를 가진 기계의 행동을 모방할 수 있을까? 모방의 대상이 되는 목표 기계들의 상태의 복잡성은 테이프 위 프로그램 암호 P 의 복잡성으로 대체된다. 프로그램 암호의 일부는 움직이는 상태 막대를 모사하기 위해 쓰이는 표시된 구획 열이다. 하나의 공백은 이 열의 위아래로 움직이며 모사되고 있는 기계의 현재 상태를 나타낸다. U 는 본질적으로 간단한 기계이다. U 는 목표 기계의 복잡성을 모방하기 위해 P 의 복잡성을 이용한다. 복잡한 프로그램이 주어지지 않은 U 는 어떤 복잡한 일도 할 수 없다.

우리가 사용하는 컴퓨터의 처리 장치는 일종의 범용 튜링 기계이다. 왜냐하면 우리가 컴퓨터에 어떤 소프트웨어를 주는 것은 사실 하나의 프로그램을 주는 것과 같기 때문이다. 이 프로그램은 자료와 함께 기억 장치에 저장이 되고, 처리 장치는 프로그램과 자료에 대해 바로 범용 튜링 기계가 테이프에 대해 작동하는 것과 마찬가지로 작동한다. 처리 장치는 특정하면서도 간단한 어떤 내장 프로그램을 가지고 있으며, 범용 튜링 기계는 간단한 범용 명령 4 중쌍의 집합을 내장하고 있다. 이것은 둘 다 <범용 컴퓨터> 로 알려져 있는 것의 예이다.

범용 컴퓨터의 특징은, 적절한 프로그램이 입력되어지기만 하면 어떤 디지털 컴퓨터의 행동도 모사할 수 있다는 것이다. <모든> 디지털 컴퓨터는 그 능력이 실제로 시간과 공간에 의해서만 제약되는 범용 컴퓨터이다. 컴퓨터에 대한 공간적 제약은 컴퓨터가 얼마나 많은 기억 장소를 가질 수 있는가와 관련이 있다. 공간적 제약을 극복하기 위해서, 흔히 컴퓨터는 여분의 가외 기억 용량을 필요로 할 때 신호를 보낼 수 있도록 만들어져 있다. 이것은 문서 작성기가 디스크의 저장 용량이 부족할 때 <디스크가 거의 찼습니다!> 라는 메시지를 표시하는 것과 똑같은 것이다. 만약 우리가 언제나 컴퓨터에 새로운 디스크를 추가할 수만 있다면, 우리의 컴퓨터는 실제적으로 무한한 기억 용량을 가지고 있는 게 된다.

비록 어떤 컴퓨터의 처리 장치가 제한된 복잡성을 가지고 있다 하더라도, 그 컴퓨터는 한 번에 한 단계씩 계산을 하고 기억 장치 안에 있는 단계들을 따라다님으로써, 임의의 복잡한 계산들을 수행할 수 있다. 이것은 기억 테이프 위의 것들을 따라다니면서 범용 튜링 기계 U 가 더욱 많은 상태를 가진 기계들의 행동을 모사할 수 있는 것과 완전히 유사한 것이다.

만약 당신이 질문을 던지고 컴퓨터로부터 대답을 듣기 위해 수십억 년을 기다릴 수 있다면, 그리고 만약 당신이 기억 장치로 사용할 여분의 디스크와 테이프를 아주 많이 가지고 있다면, 모든 디지털 컴퓨터들은 모두 만족스럽게 작동할 것이다. 이런 이유에서, 어떤 주어진 문제를 어떤 컴퓨터를 사용하여 풀 수 있느냐라는 물음은 그 문제를 어떤 튜링 기계를 사용하여 풀 수 있느냐라는 물음과 같다.

이런 고찰의 다소 놀라운 결론은 <계산 가능함> 이란 하나의 절대적이고 비관계적인 개념이다. 만약 어떤 함수 f(K) = N 의 값들이 어떤 디지털 컴퓨터를 사용하여 계산이 가능하다면, 그 값들은 범용 튜링 기계로도 계산이 가능하다. 어떤 것을 입력받은 디지털 컴퓨터가 주어지면, 우리는 언제나 범용 튜링 기계의 계산 U(P, D) 가 같은 결과를 내게 되는 프로그램 암호 P 와 자료 암호 D 를 찾을 수 있다. 반대로 말하면, 만약 어떤 계산 문제가 범용 튜링 기계로 풀어지지 않는다면, 그 문제는 어떤 디지털 컴퓨터로도 풀어지지 않는다.

7. 해결이 불가능한 문제들

괴델의 정리는, M 이 모순이 없고 유한하게 주어진 수학에 관한 어떤 논리적인 시스템인 경우에, M 이 증명하거나 부정할 수 없는 어떤 특정한 수학적인 명제 G(M) 은 언제나 존재한다는 것을 나타낸다. 논리학의 형식계들은 <증명 가능성> 이라는 모호한 개념을 명호가하게 만들어 주기 때문에 중요하다. 만약 내가 어떤 시스템의 공리와 규칙들을 알고 있다면, 나는 아주 기계적으로 그 시스템이 증명할 수 있는 모든 정리들의 목록을 만들 수 있을 것이다.

현실적으로, 사람들은 어떤 고정된 공리들의 집합으로부터 어렵게 결론을 도출해 내는 방법으로는 과학적인 발견을 하지 않는다. 어떤 주어진 명제 S 가 참일 것이라고 짐작을 한 뒤, S 를 암시하는 가장 간단하고 가능한 가설들을 찾는 일에 착수하는 것이 더욱 일반적인 과정이다. 이 가설들은 하나의 새로운 이론 M 의 일부가 된다. 그러면 이런 연구에 대한 과학적인 보고서는 1) 이론 M 에 대한 하나의 간결하고 우아한 기술, 2) M 에 포함된 가설들이 참일 것 같은 이유에 대한 설명, 그리고 3) 관심이 있는 명제 S 가 M 의 논리적인 결론이라는 것에 대한 형식적인 증명의 형태를 띨 것이다.

괴델의 정리에 따르면 이 과정은 결코 끝나지 않는다. 왜냐하면 어느 누구도 모든 것을 결정하는 최고이자 최후의 이론 M 에 도달할 수 없기 때문이다. 그런데 과학자들이 공리로부터 결과를 도출해 내는 것이 아니라 자신들이 증명하고자 하는 결과에 맞는 어떤 이론을 구축하는 반대의 과정을 선호하는 것에는 또 다른 이유가 있다. 어떤 확정된 이론 M 과 어떤 임의의 명제 S 가 주어졌을 때, S 가 M 으로부터 증명이 가능한지 아닌지를 결정하는 것은 아주 어려운 것이 사실이다. 현실적인 어려움 가운데 한 가지는 S 를 증명 (그런 증명이 설사 존재한다고 해도) 하고 그것을 이해하는 데까지 걸리는 시간이 사람에게 주어진 시간에 비해 너무나 긴 경우이다. 또한 이론적인 어려움 한 가지는 S 에 대한 증명에 도달하기까지에 걸리는 시간이 얼마나 되는지 우리는 예측할 수 없다는 것이다. 아주 간단한 명제를 증명하는 데 오랜 시간이 걸리는 경우도 아주 흔하다.

그럼에도 불구하고, 어떤 사람은 어떤 명제 S 의 증명 가능성을 검사하기 위해 빠르고 기계적인 방법을 찾기 바랄 것이다. 그 사람은 아마도 특징적인 기호 패턴들이나 이와 비슷한 것들을 찾을 것이다. 어떤 명제 S 가 어떤 주어진 이론 M 으로부터 증명이 가능한지를 결정하는 문제는 <결정 문제 (Entscheidungsproblem)> 라고 알려져 있다. 1936 년, 논리학자 앨론조 처치는 결정 문제는 해결이 불가능함을 보였다. 이 결과는 <처치의 정리> 로 알려져 있다. 처치의 정리는 어떤 명제가 M 으로부터 증명이 가능한지를 미리 예측할 수 있는 쉬운 방법은 없다고 말한다. 당신이 취할 수 있는 가장 좋은 방법은 M 을 사용하여 이것저것을 증명하기 시작하여 S 가 나오는지를 기다려 보는 수밖에 없다. 만약 S 가 실제로 증명이 가능하지 <않다면>, 당신은 언제나 S 에 대한 증명이 곧 나올 것이라고 생각하면서 영원히 기다리게 될 것이다.

처치의 정리가 의미하는 바는 어떤 형식 논리계 M 을 하나의 정리 증명 기계로 생각하면 더욱 명확해진다. 만약 내가 M 의 공리들과 추론 규칙들을 기술한다면, 나는 실제로 어떤 컴퓨터에 모든 1 단계 증명들, 모든 2 단계 증명들, 모든 3 단계 증명들 등을 제시하도록 프로그래밍할 수 있을 것이다. 공리는 도미노로, 추론 규칙은 그 도미노들을 차례로 놓는 적절한 방법들의 기술로 생각할 수도 있다. 만약 어떤 명제에 닿게 되는 도미노 패턴이 있다면, 그 명제는 M 으로부터 증명이 가능하다. 가능한 모든 증명 패턴들을 사용하고 모든 적법한 증명의 결론들을 출력함으로써, 우리의 기계는 기계적으로 모든 M 의 정리들을 만들어 낼 수 있다. S 가 M 으로부터 증명이 가능한지의 문제는 정리 증명 기계 M 이 명제 S 를 출력할 것인지의 문제와 같다.

만약 처치의 정리가 없다면, 우리는 명제 S 가 M 으로부터 증명이 가능하면 DM(S) = 1 이고 그렇지 않으면 DM(S) = 0 인 어떤 튜링 기계 또는 컴퓨터 DM 이 있을 것이라고 생각할 것이다. 그러나 처치의 정리는 결정 문제의 모든 경우들에 대해서 올바른 답을 제공하는 디지털 컴퓨터는 없다는 것을 나타낸다.

만약 우리가 M 을 컴퓨터로 간주할 수 있다고 한 것을 기억한다면, 우리는 처치의 정리가 다소 놀랄 만한 컴퓨터의 한계를 의미하고 있다는 것을 알게 될 것이다. 모든 컴퓨터 프로그램이 할 수 있는 일을 예측할 수 있는 초 프로그램은 없다. 괴델의 정리가 어떤 디지털 컴퓨터 M 도 자연수에 대해서 참인 모든 명제들을 출력하도록 프로그래밍될 수는 없다는 것을 의미하는 한, 처치의 정리는 어떤 기계 M 이 어떤 명제 S 가 참이라는 것을 증명하게 될 것인가를 예측할 수 있는 방법은 없다는 것을 의미한다.

처치와 거의 같은 시기에, 앨런 튜링은 처치의 정리와 아주 관계가 깊은 하나의 결론을 증명하였다. 즉, 어떤 기계 M 과 어떤 프로그램 P 가 주어지면, P 가 언제 실행을 끝낼지 예측하는 표준적인 방법은 없다는 것이다. 이 결론은 튜링의 정리로 알려져 있다. 이 정리에 따르면, 일반적으로 어떤 프로그램이 얼마나 오래 수행될 것인지를 찾아내는 단 한 가지의 방법은 앉아서 그 프로그램을 지켜보는 것뿐이며, 우리는 영원히 그 프로그램의 실행을 지켜보게 될 수도 있다.

튜링의 정리는 아주 실제적인 어떤 것을 우리에게 알려 주고 있다. 어떤 컴퓨터가 어떤 종류의 계산을 끝내기까지 상당한 시간이 걸리는 일은 흔하게 일어난다. 그 기계가 파손된 것이 아니라 작동 중인 상태임을 사용자에게 알리기 위해서, 컴퓨터는 흔히 여분의 시간에 잡음을 내거나 <실행 중> 과 같은 메시지를 화면에 표시한다. 예를 들어, 애플 사의 매킨토시 컴퓨터는 무언가를 작동 중일 때 모래 시계의 그림을 화면에 표시한다 (신형 컴퓨터에서는 그냥 시계가 표시된다). 내가 처음으로 애플 컴퓨터가 이런 모래 시계를 표시하는 것을 보았을 때, 나는 <모래> 가 움직이고 있는지를 보려고 화면에 좀더 가까이 다가갔다. 나는 내가 얼마나 오래 기다려야 하는지를 궁금하게 생각했다. 10 초? 10 분? 30 분? 이 컴퓨터가 어떤 무한 루프로 들어가 버려서 내가 컴퓨터를 끄지 않는 한 영원히 기다려야 하는 상황이 일어날 수도 있을까? 그때 나는 애플의 모래 시계가 정적인 아이콘이라는 것을 깨달았다. 그것은 정적인 것<이어야만> 한다. 왜냐하면, 튜링의 정리는 일반적으로 어떤 디지털 컴퓨터가 어떤 주어진 작업을 수행하는 데 얼마나 오랜 시간을 소비할지 미리 예측할 수 있는 방법은 없다는 것을 의미하기 때문이다.

튜링의 정리를 좀더 자세히 살펴보자. 처치의 정리가 어떤 컴퓨터도 결정 문제의 모든 경우를 풀 수는 없다는 것을 의미하는 것처럼, 튜링의 정리는 어떤 컴퓨터도 정지 문제의 모든 경우를 풀 수는 없다는 것을 의미한다. 정지 문제란 무엇인가? 이것은 어떤 임의의 튜링 기계가 영원히 작동할 것인가 아니면 어떤 결과를 출력하고 자신을 끌 것인가를 예측하는 어떤 일반적인 방법을 찾는 문제이다.

컴퓨터에 대한 사실 가운데 주목할 만한 것은 모든 프로그램이 작동하는 것은 아니라는 것이다. 어떤 행동 루프로 들어가 영원히 작동하면서 최종적인 결과를 내지 않는 튜링 기계의 예들은 쉽게 생각해 낼 수 있다. 어떤 주어진 프로그램 P 가 주어진 자료 집합 D 로 수행하는 계산은 P(D) 로 나타낼 수 있다. 정지 문제는 어떤 주검사 기계 C 가 어떤 프로그램 P 와 어떤 자료 D 에 대해 C(P, D) 가 다음의 결과들 중 하나를 출력할 수 있는지를 묻는 것이다.

C(P, D) = 0 ↔ 계산 P(D) 는 절대 정지하지 않는다, 그리고

C(P, D) = 1 ↔ 계산 P(D) 는 결국 정지한다.

튜링의 정리는 C 와 같은 프로그램은 없다는 것을 의미한다. 이 정리는 어떤 C 가 주프로그램 검사기 C 로서 작동하는 것이라고 생각될 때마다, C 가 정지할 것이라고 예측하면 영원히 작동하고, 영원히 작동할 것이라고 예측하면 정지하는 어떤 계산 X 를 언제나 발견할 수 있다는 것을 보임으로써 증명된다. 어떤 경우라도 C 는 X 에서 틀릴 것이므로 C 는 올바로 작동하는 주프로그램 검사기라 할 수 없다.

튜링의 증명은 괴델의 정리와 마찬가지로 자기 참조적인 요령을 사용한다. 기본적으로 X 는 <이 계산은 단지 C 가 이 계산이 정지하지 않을 것이라고 예측할 때에만 정지한다> 는 걸 의미하는 어떤 계산이다. 우리는 X 를 다음과 같이 얻을 수 있다.

먼저 C 를 사용하여 어떤 기계 C# 을 만든다. 이 기계는 프로그램 암호를 자료로 입력하고 0 과 1 의 역할을 바꾼다.

C(P, P) = 0 → C#(P) 는 정지한다.

C(P, P) = 1 → C#(P) 는 절대 정지하지 않는다.

그리고 우리가 암호 C# 을 기계 C# 에게 줄 때 일어나는 계산을 X 라 하자. 다시 말해서 X 는 계산 C#(C#) 이다.

C 는 X 가 절대 정지하지 않을 것이라고 예측한다. ↔ C(C#, C#) = 0

                                                                 → C#(C#) 은 정지한다.

                                                                 ↔ X 는 정지한다.

                C 는 X 가 정지할 것이라고 예측한다. ↔ C(C#, C#) = 1

                                                                 → C#(C#) 은 절대 정지하지 않는다.

                                                                 ↔ X 는 절대 정지하지 않는다.

그림 117  정지 문제의 해결 불가능성에 대한 튜링의 증명. i) <P(D) 정지> 는 프로그램 P 와 자료 D 를 가진 튜링 기계가 계산을 수행하고 자신을 끔을 의미한다. <P(D) 수행> 은 자료 D 를 가진 기계 P 가 영원히 작동됨을 의미한다. 만약 정지 문제가 해결 가능하다면, (P, D) 를 입력으로 취하여 만약 (P, D) 가 정지하면 1 을 출력하고, (P, D) 가 진행하면 0 을 출력하는 어떤 기계 C 가 존재할 것이다. ii) C 가 i) 에서와 같이 주어진다면, 우리는 표시된 바와 같이 C# 을 만든다. <복사기> 는 어떤 프로그램 P 를 취하여 그것을 복사하고 하나의 (프로그램, 자료) 쌍 (P, P) 를 출력한다. <작동> 기계는 1 이 입력되면 영원히 회전하는 바퀴를 켠다. <정지> 기계는 0 이 입력되면 전원 플러그를 뽑아 모든 것을 끌 수 있는 장치를 가지고 있다. C# 은 P(P) 가 정지하면 C#(P) 가 작동하고, P(P) 가 작동하면 C#(P) 가 정지하는 성질을 갖고 있다. iii) 이제 우리는 표시된 바와 같이 어떤 기계 X 를 만든다. X 는 C#(C#) 계산을 한다. 만약 X 는 정지할 것이라고 C 가 예측한다면 X 는 수행된다. 만약 X 는 수행될 것이라고 C 가 예측한다면 X 는 정지한다. 그러므로 C 는 정지 문제에 대한 올바른 해답을 제공하지 않는다.

정지 문제의 해결 불가능성은 어떤 프로그램이 적절하게 작동할 것인가를 미리 올바로 예측할 수 있는 컴퓨터 프로그램은 없다는 것을 의미한다. 이 결과의 <따름 정리> 는 임의로 선택된 프로그램들이 얼마나 <오래> 수행될지를 추정할 수 있는 방법은 없다는 것이다. 다시 말해서, P(K) 의 계산이 정지한다고 할 때 그 정지하는 시기는 N 단계 이전이라는 것을 의미하도록 정의되는 수행 시간 추정 프로그램 R(P, D) = N (여기서 P 는 어떤 프로그램을, D 는 어떤 자료를 가리킴) 은 존재하지 않는다는 것이다.

그런 프로그램 R 이 존재하지 않는 이유는, 만약 그것이 존재한다면 우리는 그것을 이용하여 주프로그램 검사기 C 를 만들 수 있게 되기 때문이다. 어떤 임의의 P 와 D 가 주어지면, 우리는 R 을 사용하여 수 N = R(P, D) 를 계산할 수 있을 것이고, 만약 그 계산이 N 단계 안에 멈추지 않는다면 우리는 그 계산이 절대 멈추지 않을 것이라는 것을 알게 될 것이며 C(P, D) = 0 으로 규정할 수 있을 것이다.

이 마지막 결과가 왜 애플의 <대기> 아이콘이 움직이지 않는가에 대한 이유를 설명하는 것이다! 이 결과의 좀더 깊은 의미는, 어떤 임의의 프로그램의 결과를 예측하는 빠른 편법은 없다는 것이다. 물론, 어떤 프로그램들은 쉽게 예측이 가능하다. 예를 들어, 주어진 문서의 어떤 페이지에 어떤 내용이 담겨 있더라도, 나는 내 문서 작성 프로그램이 그 문서를 몇 초 안에 복사할 수 있을 것이라는 것을 알고 있다. 그러나 만약 내가 알려지지 않은 좀 복잡한 어떤 프로그램을 가지고 있다면, 그 프로그램이 무엇을 하는 프로그램인가를 알아보는 방법은 대부분 실제 그것을 <실행> 해 보는 방법밖에는 없을 것이다.

이 발견은 물리학의 영역에서 몇 가지의 놀라운 반향을 얻고 있다. 아주 많은 부분들로 이루어진 물리학적인 하나의 시스템은 어떤 복잡한 프로그램을 지닌 하나의 디지털 컴퓨터로 생각할 수 있다. 이론을 고안하는 물리학자들은 보통 자신들이 흥미를 가지는 시스템들이 무엇을 할 것인가를 예측하는 간단한 방법을 찾으려고 노력하지만, 만약 어떤 물리학적인 시스템이 하나의 범용 컴퓨터와 같은 것이라면, 튜링의 발견은 우리에게 그 시스템들이 무엇을 할 것인가를 예측하는 간단한 방법은 <없다> 는 것을 알려 준다!

수학의 많은 일반적인 문제들은 정지 문제의 특별한 경우들로 생각할 수 있다. 수백 년 동안, 사람들은 골드바흐의 추측 (Goldbach's conjecture) 에 대해 궁금하게 여겨 왔다. 골드바흐의 추측이란 모든 짝수는 두 개의 소수의 합일 것이라는 추측을 말한다. 수학자들은 1 억까지의 모든 짝수들에 대해 검사를 했고, 지금까지 이 수들은 모두 두 개의 소수의 합으로 나타낼 수 없는 어떤 짝수가 있을 수도 있지 않을까? 그런 수의 존재에 대해 의문을 가지는 것은 어떤 특별한 튜링 기계가 정지할 것인가에 대해 의문을 가지는 것은 어떤 특별한 튜링 기계가 정지할 것인가에 대해 의문을 가지는 것과 같다. 짝수들을 하나씩 검사하면서 각 수 N 마다 N 보다 작으면서 그 합이 N 이 되는 두 개의 소수의 합이라면, G 는 N 보다 큰 다음의 짝수를 검사한다. 만약 N 이 두 개의 소수의 합이 아니라면, G 는 N 을 출력하고 정지한다. 골드바흐의 추측은 이런 튜링 기계 G 가 절대로 정지하지 않아야만 참이 된다. 만약 G 의 프로그램을 보고 그 기계가 정지할지를 결정할 수 있는 어떤 방법이 있다면, 그것은 골드바흐의 추측에 대한 답을 줄 수 있는 방법이 될 것이다.

결정 문제의 각 예들은 또한 정지 문제의 예들이 될 수 있다. 예를 들어, 만약 내가 잘 알려진 수학의 공리들에 근거하여 어떤 난해한 추측을 증명하는 게 가능한지 알고 싶다고 해보자. 나는 차례로 점점 더 큰 수 N 을 집어서 N 이 그 추측을 올바로 증명할 수 있는 L27 암호가 되는지 검사하는 어떤 튜링 기계 C 를 설계할 것이다. 만약 N 이 정말로 어떤 증명을 암호화한다면 C 는 1 을 출력할 것이고, 만약 그렇지 않다면 C 는 다음으로 큰 N 에 대해 조사를 할 것이다. 만약 내가 C 가 정지할 것이라는 것을 알게 된다면, 나는 내 추측에 대한 증명이 존재한다는 것을 알게 될 것이다. 만약 내가 C 는 정지하지 않을 것이라는 것을 알게 된다면, 나는 내가 가지고 있는 공리들을 이용하여 나의 추측을 증명하려는 노력을 포기해야만 함을 알게 될 것이다.

정지 문제보다 훨씬 간단해 보이면서도 해결이 불가능한 문제로는 몇 가지 종류가 더 존재한다. 힐버트의 열 번째 문제 (Hilbert's thenth problem) 로 알려진 다음의 문제는 이런 문제의 좋은 예다. 이 문제는 어떤 임의의 대수 방정식이 어떤 정수 해를 갖는가를 알아보는 것이다. 은 정수 해 3 을 갖는 대수 방정식의 예이고, 은 어떤 정수로도 만족되지 않는 방정식이다. 한때 힐버트는, 주어진 대수 방정식을 조사하여 정수 해를 갖는지를 결정하는 어떤 기계적인 방법이 존재할 것이라고 생각했다. 그러나 아주 최근에 수학자들은 이 일반적인 문제는 해결이 불가능하다는 것을 증명했다. 다시 말해, 방정식 A 가 정수 해를 가질 때에만 P(A) = 1 이 되는 프로그램 P 는 존재하지 않는다.

8. 진실의 바다

많은 종류의 문제들은 어떤 수들이 어떤 특별한 성질을 가지고 있는가를 결정하는 문제로 볼 수 있다. 따라서, 모든 명제를 하나의 수로 암호화하는 것을 생각할 때, 진실의 문제는 어떤 수들이 참인 명제들의 암호 수로서의 자격이 있느냐의 문제가 된다. 어떤 주어진 수가 우리가 알고자 하는 성질을 가지고 있는지 아닌지를 확인해 볼 수 있는 프로그램을 만들 수 있다면, 그 성질은 <계산 가능> 하다고 말할 수 있다. 프로그램 P 가 주어진 범용 튜링 기계의 개념을 사용하면 우리는 이 성질을 아주 정확하게 표현할 수 있다. 수에 대한 어떤 성질 R 은 다음과 같은 프로그램 P 가 존재하면 계산이 가능하다고 한다.

N 은 성질 R ↔ P(N) = 1 을 가지고 있고,

N 은 성질 R ↔ P(N) = 0 을 가지고 있지 않다.

마지막 절에서 우리는 <정지하는 튜링 기계의 암호 수가 되는 것> 은 계산이 가능하지 않다는 것을 발견하였다. 비록 영원히 실행되지 않는 프로그램이 된다는 성질은 계산이 가능하지 않지만, 이 성질을 가진 프로그램들의 <목록을 작성할 수는 있다>. 다시 말해서, 결국은 정지하게 될 모든 프로그램의 목록을 작성하는 튜링 기계는 존재한다. 수에 대한 어떤 성질 R 은 다음과 같은 프로그램 P 가 존재할 때 목록화가 가능하다고 한다.

N 은 어떤 수 K 에 대해서 성질 R ↔ P(K) = N 을 가지고 있다.

정지하는 모든 프로그램들의 집합은 목록화가 가능하다. 왜냐하면, 어떤 수 K 가 주어지면, 프로그램을 하나씩, 그리고 점점 더 오랜 시간 동안 검사하여, 정지하는 프로그램을 K 개 찾아 이 프로그램들 중 K 번째 프로그램에 대한 암호 수를 출력하고, 정지하는 어떤 기계를 조립하는 것을 상상할 수 있기 때문이다.

아주 흥미롭게도, 수에 대한 어떤 참인 명제의 암호 수는 목록화를 할 수도 없고 계산이 가능하지도 않다. 어떤 프로그램도 수에 대한 참인 명제들과 거짓인 명제들을 구별하도록 설계될 수 없을 뿐만 아니라, 어떤 프로그램도 거짓인 명제들을 포함시키지 않고 모든 참인 명제들을 목록화하도록 설계될 수 없다.

만약 어떤 성질이 계산 가능하다면, 이것은 어떤 N 이 그 성질을 가지고 있는지에 대해 예 또는 아니오로 대답을 할 수 있는 기계적인 프로그램 P 가 존재한다는 것을 의미한다. <소수임> 은 계산 가능한 성질의 한 예이다. 왜냐하면 나는 어떤 주어진 수 N 을 N 보다 작은 각 수들로 나누는 것을 시도할 수 있기 때문이다. 만약 N 이 소수라면, 이 수들 중 어떤 것도 N 을 나눌 수 없을 것이고, N 이 소수가 아니라면, 1 이 아닌 어떤 수로 N 을 나눌 수 있을 것이다. <항진 명제의 암호 수임> 은 계산 가능한 성질의 또 다른 예이다. 어떤 복합 명제 S 의 암호 수가 주어지면, 나는 하나의 진리치표를 만들어 S 가 그 다양한 절들의 참과 거짓에 관계없이 항상 참이 되는지를 조사할 수 있다.

따라서 어떤 수에 대한 성질 R 은 만약 내가 확실하게 성질 R 의 존재 또는 부재를 탐지할 수 있는 튜링 기계를 만들 수 있을 때 계산이 가능하다. 비유적으로 말하면, 금속을 소유한 사람이라는 성질은 계산이 가능한 성질이다. 금속 탐지기는 지정된 어떤 사람에 대해 그 사람이 금속을 소지하고 있는지 아닌지를 탐지할 수 있다. 만약 그 사람이 금속을 소지하고 있다면 탐지기에는 빨간 불이 들어올 것이고, 그 사람이 금속을 소지하고 있지 않다면 탐지기에는 녹색 불이 들어올 것이다.

만약 어떤 성질의 목록화가 가능하다면, 이것은 그 성질을 가지는 모든 수들을 목록화할 수 있는 어떤 기계적인 프로그램 P 가 존재한다는 것을 의미한다. <이론 M 의 어떤 정리를 암호화하는 수임> 은 목록화가 가능한 성질의 한 예이다. 왜냐하면, 어떤 이론 M 이 주어지질 때 나는 M 의 모든 결과들을 조직적으로 유도할 수 있기 때문이다. 만약 그 수 N 이 M 의 어떤 정리를 암호화한다면, 나는 결국 그 정리에 도달하게 될 것이다. 어떤 짧은 정리에 대한 증명은 아주 길어질 수도 있다. 따라서 내가 아직 어떤 정리 N 을 증명하지 않았더라도, 나는 항상 나중에 N 이 증명될 것인지 아닌지에 대해 궁금하게 여겨야만 한다.

<구원받음> 이라는 성질이 목록화가 가능하다고 상상해 보자. 최후의 심판의 시간에, 천국의 문 앞에는 사람들이 줄을 지어 서 있다. 성 베드로는 아주 친절하기 때문에 절대 누군가를 보고 <당신은 저주받았고. 지옥으로 가시오> 라고 말하지 않는다. 대신에, 그는 구원을 받기 위한 조건의 무한한 목록을 말하기 시작한다. <좋소. 만약 당신이 어떤 사람의 생명을 구했다면, 천국에 온 걸 환영하겠소. 부랑자에게 10 달러를 준 사람은 이리로 오시오. 1946 년에 태어난 사람도 이쪽으로 오시오. 나는 1946 년을 좋아하오. 좋소. 만약 당신이 가난하게 죽었다면 천국으로 들어갈 수 있소. 스킨 다이버인 사람 누구 있소? 모든 스킨 다이버는 구원받았소.> 게속해서 그는 구원을 받기 위한 자격의 무한한 목록을 말한다. 만약 당신이 구원받을 조건을 가지고 있다면, 당신은 결국 구원받을 것임을 알게 될 것이다. 그러나 만약 당신이 저주받았다면, 당신은 당신이 구원받을지에 대해 영원히 확신하지 못한 채 그곳에 서 있게 될 것이다.

계산이 가능한 성질들과 목록화가 가능한 성질들의 구별은 아직도 약간 모호하게 느껴질 수 있다. 도대체 왜 나는 이런 구별의 문제를 논하는 것인가? 그 이유는, 논리학에서 우리가 관심을 갖는 대부분의 형식계들, 즉 모든 시스템 이론의 집합은 목록화가 가능하지만 계산은 불가능하기 때문이다. 다시 말해서, 우리는 어떤 좋은 논리적 시스템 M 의 모든 정리들에 대해서 목록을 만들 수는 있지만, 어떤 명제 S 를 보고 그 S 가 하나의 증명인지를 자동적으로 알 수 있는 유한한 기계적인 방법을 찾을 수는 없다. 내가 언급했듯이, 이런 유한한 프로그램은 존재하지 않는다는 것이 1936 년에 앨론조 처치에 의해 증명이 되었고, 이것은 지금 처치의 정리로 알려져 있다.

만약 모든 수학이 어떤 이론 M 으로 성문화되어 있다고 가정하면, <M 의 《공리》임> 이라는 성질은 계산이 가능한 하나의 성질이 될 것이다. 우리가 사용하는 공리들은 간단한 도식들의 유한한 모임으로 구분할 수 있으며, 공리의 어떤 후보 S 를 그 도식들에 대해 점검하는 것은 분명한 <예> 또는 <아니오> 의 결과를 유한한 시간 내에 낼 수 있는 기계적인 과정이다.

어떤 명제가 M 으로부터 증명이 가능한지를 결정하는 것은, 주어진 명제의 증명이 얼마나 오래 걸릴지를 예측할 수 있는 방법이 없기 때문에 좀더 어렵다. 처치의 결과는, M 의 <정리> 가 된다는 것은, 목록화는 가능하지만 계산은 불가능한 성질이라는 것을 의미한다.

<수학적 언어 M 으로 된 《참인 명제》임> 이라는 성질은 좀더 알기가 어렵다. 괴델의 정리에 따르면 이 성질은 목록화조차 가능하지 않다.

따라서 성질의 종류에는, 점점 더 복잡해지는 순서대로 계산이 가능한 성질, 목록화가 가능한 성질, 그리고 계산도 불가능하고 목록화도 불가능한 성질의 세 가지 범주가 있다는 것을 알 수 있다. 세 번째의 성질을 <기대되는> 성질이라고 부른다고 하자. 공리들의 집합은 계산이 가능하고, 정리들의 집합은 목록화가 가능하며 진실들의 집합은 기대할 수 있다 (그림 118 참조).

그림 118  처치의 정리는 목록화가 가능한 어떤 성질들은 계산이 불가능하다는 것을 증명한다. 괴델의 정리는 기대되는 prospective 어떤 성질들은 해석할 constructive 수 없다는 것을 증명한다.

<기대되는 prospective> 이라는 용어는 존 마이힐 (John Myhill) 의 1952 년도 논문 「수학적 논리학의 철학적 의미, 사고의 세 가지 종류 (Some Philosophical Implications of Mathematical Logic : Three Classes of Ideas)」로부터 취한 것이다. 틀에 박히고 형식적인 1950 년대를 생각할 때, 마이힐은 이 논문에서 아주 비법한 일을 했다. 그는 처치의 정리와 괴델의 정리를 어떤 은유적인 방식으로 생각할 수 있다는 것을 증명하였다.

처치와 괴델에 따르면 공리, 정리, 그리고 진실은 세 가지의 서로 다른 복잡성을 갖는다. 마이힐은 이 같은 세 가지 구분이 다른 곳에서도 많이 발견된다는 것을 지적했다.

이 페이지와 같이 글자, 공백, 그리고 구두점들로 덮인 어떤 인쇄된 페이지 S 를 생각해 보자. 이 페이지가 문법에 맞는 영어로 씌어졌는가는 계산이 가능한 문제이다. 사용된 단어들이 모두 사전에 있는 단어들인지, 그리고 문장들이 전통적인 문장 형태에 들어맞는지를 검사하기만 하면 된다.

비록 페이지 S 가 문법에 맞는 영어로 씌어져 있다고 해도, 그것은 당신에게 전혀 의미가 없을 확률이 아주 높다. 이것은 이 페이지가 횡설수설로 씌어져 있기 때문이거나, 당신이 이 페이지에서 언급하는 개념들에 친숙하지 않기 때문일 수 있다. 당신은 S 가 당신에게 의미가 있는지를 결정하는 유일한 심사원이다. 일반적으로, 당신이 오래 살면 오래 살게 도리수록, 서로 다른 페이지 S 들은 더욱 의미가 있게 될 것이다. 그러나 어떤 페이지들이 결국 당신에게 의미가 있게 될 것인가를 예측하는 것은 불가능하다. 의미가 있음이라는 성질은 목록화는 가능하지만 계산은 불가능하다.

마찬가지로, 어떤 페이지 S 가 당신이 <쓰고 싶은> 면이 될 것인가라는 질문은 목록화가 가능하다. 한 작가의 저술은 그의 끝없는 두뇌 회전으로부터 다소 기계적인 방식으로 만들어진다. 한 사람의 작가로서, 나는 <내가 이것을 말하고 있다니!> 라고 말한 적이 얼마나 많았던가. 이것은 말을 함에 있어서도 마찬가지이다. 다시 말해, 어떤 문자 열이 당신이 결국 말하고 싶어할 문장이 될 것이라는 성질은 목록화가 가능하지만 (당신의 전 생애를 통하여 당신은 이 문장들을 <목록화> 하고 있다), 계산은 분명히 불가능하다.

진실, 미, 또는 미덕과 같이 더 고차원적인 성질들은 게산도 목록화도 할 수 없는 것들이다. 우리가 참인 것, 아름다운 것, 또는 좋은 것을 인식하는 데에는 어떤 정해진 규칙도 없다. 이런 인간의 이상들은 계산이 불가능하다. 어떤 개인이나 학파로 하여금 모든 진실, 모든 미 또는 모든 미덕을 제시할 수 있도록 하는 프로그램은 아무것도 없다. 우리가 바랄 수 있는 가장 좋은 목표는 어떤 하나의 시스템에 대해 논리적으로 연구하려다가 완전히 지치지 않게 되는 것뿐이다.

처치의 정리는, 어떤 간단한 검사도 중요한 문제들에 대해 <예> 또는 <아니오> 의 대답을 할 수 없다는 첫번째의 사실에 대한 하나의 구체적인 예이다. 그리고 괴델의 정리는, 어떤 논리적인 프로그램도, 궁극까지 추구한다 할지라도, 모든 문제들에 대해 대답하는 것을 바라서는 안 된다는 두 번째의 사실에 대한 하나의 구체적인 예이다.

튜링, 처치, 그리고 괴델의 연구 이후, 하나의 유한한 논리적인 그물로 모든 질실을 잡겠다는 오래된 꿈은 완전히 파괴된 것으로 볼 수 있다. 계산에 대한 튜링의 분석은 유한하게 주어진 모든 논리적 시스템 (인간을 포함하여) 은 괴델과 처치의 정리들의 지배를 받는다는 것을 시사한다. 괴델의 정리는 어떤 프로그램적인 방법도 모든 진실을 만들어 낼 수는 없다는 것을 의미한다. 한편 처치의 정리는 우리가 만들어 낸 프로그램의 결과를 예측할 수조차 없다는 것을 의미한다. 이것이 우리가 절망할 만한 이유가 될까? 실제로는 그렇지 않다. 이것은 오히려 우리가 기뻐해야 할 이유라고 나는 말하고 싶다.

괴델의 정리가 없는 세계는 모든 특성이 목록화가 가능한 세계일 것이다. 이런 세계에서는, 어떤 종류의 인간 행동을 어떻게 수행해야 하는가 하는 하나의 프로그램적인 기술이 있을 것이다. 이런 세계에서는 <예술가가 되는 법> 이나 <과학자가 되는 법> 에 대한 명확한 공식을 배우는 것이 가능할 것이다. 예술가나 과학자가 되는 법을 배우는 것은 사용되는 기술을 배우는 문제가 될 것이다.

괴델의 정리와 처치의 정리가 없는 세계는 모든 특성을 계산할 수 있는 세계일 것이다. 이런 세계에서는 어떤 종류의 인간 활동에 대해서도 그 결과가 어떨 것인지를 결정할 수 있는 정해진 방법이 있을 것이다. 그런 세계의 예술원은 무엇이 예술이고 무엇이 과학인지에 대한 판단을 내릴 수 있을 것이다. 창조성은 예술원의 규칙에 따른 측정의 문제가 될 것이고, 낙선전은 오직 쓰레기들만을 전시하게 될 것이다.

그러나 예술의 역사가 우리에게 가르치는 것이 한 가지 있다면, 그것은 모든 기술은 싫증이 나게 마련이므로 낙선전을 항상 주시하라는 것이다.

우리의 세계는 어떤 유한한 프로그램이나 어떤 유한한 규칙들의 집합보다 무한하게 더 복잡하다. 당신은 자유롭다. 그리고 당신은 정말로 살아 있다. 당신이 다음에 무엇을 생각할지를 알 수 있는 방법은 없으며, 당신이 속박을 벗어나서 언제든지 새로운 인생을 시작하지 못할 어떤 이유도 없다.