이 글은 초안입니다.

컴퓨터 연대기 시리즈 목록

기본적으로는 2주에 한번씩 연재할 계획이다. 다만 취미로 하는 작업이기 때문에 사정에 따라 연재가 늦어지거나 주기가 바뀔 수 있다.

시리즈	링크
컴퓨터 연대기 0. 서문	링크
컴퓨터 연대기 1. 생각하는 기계를 향한 첫걸음, 추론의 기초를 세운 사람들	링크
컴퓨터 연대기 2. 논리로 세상을 설명하려 한 사람들과 그들이 마주한 역설	링크

• 조사를 위해 노력했지만, 혹시 틀린 부분이 있다면 댓글 등을 통한 지적을 환영합니다.

모든 걸 포괄하는 체계를 향해

불은 논리를 기호로 표현할 수 있는 체계를 만들었고 논리적인 관계를 수학으로 다룰 수 있는 기초를 세웠다. 사실상 수학의 한 분야를 처음 열었다. 이 분야는 오늘날에도 불 대수라고 불린다.

하지만 불이 만든 체계는 아직 구조적으로 불완전했다. 불의 체계로 나타낼 수 없는 논리적 표현이 있었기 때문이다. 예를 들어 "모든 학생은 멍청하거나 게으르다.¹" 같은 단순한 문장조차 완벽히 표현할 수 없었다.

이 문장을 앞 글에서 썼던 불의 기호만으로 서술하려고 시도해 보자. 가령 $A, B$를 다음과 같이 정의하면 어떨까?

• $A$: 모든 학생은 멍청하다.
• $B$: 모든 학생은 게으르다.

그럼 불의 표현을 써서 위 문장을 $A + B = 1$로 쓸 수 있지 않을까 하는 생각이 든다. 하지만 그렇게 표현하면 멍청한 학생과 게으른 학생이 섞여 있는 경우를 포괄하지 못한다.

이렇듯 당시 논리 체계는 라이프니츠의 꿈처럼 세상 모든 걸 표현할 수 있는 체계와 아직 거리가 멀었다. 이를 채우기 위해 그리고 더 나아가기 위해서 시도한 사람들을 이제부터 알아보자. 이런 시도는 결국 완전히 좌절되며 이 좌절은 수학계에 큰 충격을 준다. 하지만 좌절이 충격적이었다는 건 반대로 말하면 이들이 그만큼 멀리 갔다는 뜻이다.

프레게의 개념 표기법, 논리 표현의 완성

논리학에 대한 프레게의 최대 공헌은 "모든"이나 "어떤" 등의 표현에 타당성을 의존하는 추리를 기호화하고 정확하게 나타내는 방법인 양화 이론(quantification theory)을 창안한 것이다. (...) 칸트의 시대에 이르기까지 논리학의 모든 것으로 간주되던 전통적인 아리스토텔레스의 삼단논법보다 더욱 엄밀하고 일반적인 방식으로 추리 이론을 형식화했다.

앤서니 케니 지음, 김영건 외 옮김, "서양 철학사", 2004, 이제이북스, 354-355쪽

1879년 예나 대학의 교수² 고틀로프 프레게(Gottlob Frege)는 "개념 표기법(Concept Notation)"이라는 소책자를 출간했다. 그는 이 책자에서 수학에서 사용하는 모든 연역 추론을 포함하는 논리 체계를 제시했다. 이 체계는 오늘날 수학에서 사용되는 $\forall,\,\exists$와 같은 양화사(quantifier)를 포함하고 있다.³

프레게는 오늘날에도 쓰이는 다음과 같은 기호들을 소개했다.

기호	의미
$\forall$	모든(every)
$\exists$	어떤(some)
$\neg$	아닌(not)
$\land$	그리고(and)
$\lor$	또는(or)
$\supset$	...이면 ...이다(if ... then ...)

그러면 앞서 소개한 문장("모든 학생은 멍청하거나 게으르다.")은 다음과 같이 표현할 수 있다.

$$\forall x ((x \in \text{학생}) \supset (x \in \text{멍청하다} \lor x \in \text{게으르다}))$$

프레게는 이렇게 수학적인 사실들을 기호로 표현하는 데에서 멈추지 않았다. 불은 수학의 기호들을 논리 관계에 사용했지만 프레게는 반대로 모든 수학의 기반에 있는 탄탄한 논리 체계를 세우고자 했다. 이 말은 프레게는 논리를 개발하는 과정에서 기존의 논리를 사용할 수 없었다는 뜻이다.

따라서 그는 논리적인 추론을 기호 패턴의 단순한 기계적 처리로 대체하고자 하는 시도를 했다. 기호들이 어떤 의미를 가지는지에 상관없이 기호들 간의 관계를 처리하는 법칙을 세우고 거기에 의미를 부여해서 쌓아 나가면 그런 논리의 힘만으로 수학의 모든 체계를 세울 수 있다는 거였다.

모든 수학적 발전을 논리로 환원하고자 하는 꿈이었고 "개념 표기법"이 그 꿈에 대해 프레게가 내놓은 결과물이었다. 이후 살펴볼 약점이 있었지만 이건 불의 논리 체계에 비하면 엄청난 발전이었다. 수학적인 논리 체계가 이제 이론적으로는 수학의 모든 추론을 포괄할 수 있게 되었기 때문이다.

이렇게 모든 수학이 논리적인 공리로 환원될 수 있다는 관점은 "논리주의(logicism)"라고 불렸으며 러셀, 데데킨트, 비트겐슈타인 등 여러 위대한 학자들에게 영향을 미쳤다.

하지만 프레게가 만든 오늘날의 모든 논리 체계와 철학에서의 태산같은 업적에도 불구하고 그의 꿈은 이루어지지 못했다. 그의 논리 체계에서 모순이 발생할 수 있다는 걸 러셀이 "러셀의 역설"로 1902년 지적했기 때문이다.

프레게는 평생 이 충격에서 헤어나오지 못했다. 그는 자신의 평생 연구가 헛된 일이었다고 믿으며 이후에는 수학의 근본에 관한 중요한 연구를 하지 않았다. 또한 이후 사회민주주의자, 가톨릭 등에 대해 적대적인 태도를 보였고 반유태주의에도 빠졌다.

프레게는 그렇게 극단적인 우파 활동으로 생의 나머지 몇십 년을 보내다가 1925년 생을 마감한다. 학계는 그의 죽음을 무시했다.

칸토어

증명된 사실과 엄밀한 추론은 견고한 과학적 지식의 기반이 된다. 감정이나 의견, 그리고 새로운 아이디어에 대한 본능적인 거부감은 그렇지 않다.

닐스 알 바리첼리, "Numerical Testing of Evolution Theories: Part II", 1963, p. 7⁴

라이프니츠의 시대에 수학자들은 오늘날 "극한"이라 부르는 개념을 다루기 시작했다. 어떤 수열이 무한대의 항까지 간다면 어떤 수에 가까워지는지 나타내는 개념이다. 라이프니츠 또한 이러한 극한을 다루었고 다음과 같이 수렴하는 무한급수를 발견하기도 했다.

$$\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \frac{1}{11} + \cdots$$

1845년 부유한 사업가의 아들로 태어난 독일계 러시아인 수학자 게오르크 칸토어(Georg Cantor)도 이를 연구했다. 그의 수학적 능력을 알아본 당대의 수학자 에두아르트 하이네가 무한급수를 포함한 문제들을 연구하자고 설득했기 때문이다. 칸토어는 사인함수와 코사인함수들을 급수 항으로 포함하는 삼각급수의 수렴에 대해 연구했으며 자연스럽게 무한에 대해 자세히 살펴보게 된다.

이전까지 수학자들은 완전한 무한을 제대로 다룰 수 없다고 생각했다. 완전한 무한이란 신의 영역이라고 생각했기 때문이다. 인간은 완전한 무안을 다룰 수 없으며 그저 극한을 이해하는 방법의 하나로써 무한을 사용한다고 보았다. 수학에 위대한 업적을 남긴 당대의 수학자 가우스조차 무한이 수학에서 절대 있을 수 없고 극한을 설명하는 방식일 뿐이라고 이야기했다.

그래서 당시 수학자들은 무한을 직관적인 영역에서만 다룰 뿐이었다. 예를 들어 우리는 다음과 같은 수열이 분모가 증가하며 "무한히" 계속된다면 0으로 수렴할 거라는 걸 직관적으로 알 수 있다.

$$1,\;\frac{1}{2}, \;\frac{1}{3},\;\frac{1}{4},\;\cdots$$

당시 수학자들이 무한을 다루는 방식이란 그 정도였다. 무한소는 말 그대로 무한히 작은 것이었고 무한히 많다는 건 그냥 셀 수 없이 많다는 뜻이었다. 거기에 도전한다는 건 유클리드, 뉴턴과 같은 위대한 학자들에 대한 도전이자 신의 영역으로 여겨졌다. 하지만 칸토어는 바로 그러한 점에 도전했다. 누구도 손대려 하지 않던 무한을 수학에서 구체적으로 다뤄보려고 시도한 것이다.

칸토어는 무한 간의 크기 차이를 가려보고자 했다. 그 결과 자연수 집합, 짝수 집합, 유리수 집합, 심지어는 모든 대수적 수(대수학적인 방정식의 근으로 나타날 수 있는 수)의 집합까지도 크기가 같다는 걸 증명했다. 그리고 실수 집합은 자연수 집합보다 크기가 크다는 사실도.

실수 집합이 자연수 집합보다 크다는 걸 증명할 때 칸토어가 사용한 방법이 대각선 논법이다. 이후 대각선 논법은 튜링의 범용 기계를 이용한 불완전성 정리 증명에도 쓰이게 된다. 이 자세한 내용에 관해서는 역사보다는 이론에 치중한 다른 글에서 다룰 예정이다.

어쨌든 이건 굉장히 새롭고 또 급진적인 생각이었다. 전체가 그 일부분보다 크다는 건 유클리드 시대부터 믿어왔던 수학의 기본 원리 중 하나였기 때문이다. 이렇게 칸토어는 무한의 세계를 집합과 함께 탐구해 나갔다. 그동안 무한의 영역에 발을 들인 사람은 없었으며 칸토어가 이러한 연구에서 의지할 만한 선대의 수학적인 이론은 존재하지 않았다. 오늘날 집합론이라는 분야에서 그의 연구 결과 대부분이 여전히 유효하게 작동하는 걸 생각할 때 이건 정말 놀랍다.

하지만 그의 작업은 당대 수학자들에게 환영받지 못했다. 직관적이지도 않았으며 유한한 존재인 인간이 무한을 다루려고 한다는 이유였다. 심지어 그의 스승 크로네커조차 그의 의견에 동의하지 않았다. 이로 인해 칸토어는 생애 후반부 내내 우울증에 시달렸다. 또한 셰익스피어 희곡의 진짜 작가가 프랜시스 베이컨이라는 음모론에 빠져 있다가 1918년 정신병원에서 쓸쓸히 세상을 떠났다.

게다가 칸토어가 쌓아올린 무한의 세계 또한 균열을 품고 있었다. 집합을 통해 무한을 다루고자 한 논리를 응용할 경우 생겨나는 여러 역설들 때문이었다. 프레게가 마주했던 러셀의 역설 또한 그 중 하나였다.

러셀의 역설

이 문장은 거짓이다.

거짓말쟁이 역설(Liar Paradox)

그럼 프레게와 칸토어의 시도를 절망시킨 이 러셀의 역설이란 뭐였을까? 1900년대 초반부터 약 1930년대까지 수학의 근본을 뒤흔들 수 있는 역설들과 그것들을 넘어 수학을 다시 견고한 기반 위에 세우고자 하는 시도들⁵이 계속된다. 이 중 커다란 영향을 미친 하나가 바로 러셀의 역설(Russell's Paradox)이다.

이건 사실상 "이 문장은 거짓이다"와 같이 자기언급이 불러오는 역설이다. "이 문장이 거짓이다"라는 문장이 참이라면 거짓이고, 거짓이라면 참이라는 식이다. 프레게는 말장난 같기도 한 이 역설이 자신의 체계에서 모순을 불러온다는 걸 알아채고 절망했다.

러셀의 역설의 정확한 설명은 다음과 같다. 먼저 "원소에 집합 자신이 포함된 집합"을 특별 집합이라고 하자. 프레게와 칸토어의 논리 체계에서 이런 집합은 허용된다. 그리고 특별 집합이 아닌 집합은 일반 집합이라 한다. 이제 모든 일반 집합의 집합 $\epsilon$을 생각할 수 있다.

그럼 $\epsilon$은 일반 집합인가 특별 집합인가? 어느 쪽으로 생각해도 모순이 있다. $\epsilon$이 일반 집합이라면 $\epsilon$에 포함되어야 하므로 자기 자신을 포함하고 따라서 특별 집합이 되어야 한다. $\epsilon$이 특별 집합이라면 자기 자신을 포함하므로 $\epsilon$의 정의상 $\epsilon$는 일반 집합이어야 한다.

프레게와 칸토어는 자연수와 그 연산의 정의를 할 때 집합의 집합 개념을 사용했다. 하지만 앞서 보았듯이 집합의 집합이라는 개념은 이런 모순을 불러온다. 따라서 이러한 집합론은 그 자체로 모순 없는 완전한 체계가 아니며 수학의 완벽한 기초를 세우는 주춧돌이 될 수 없다.

프레게가 개념 표기법으로 제시한 논리 체계와 칸토어의 집합론 위에 수학을 그 자체로 완전하게 세우려는 꿈은 이렇게 끝났다. 물론 많은 수학자는 이를 뒤로한 채 하던 연구를 계속해 나갔다. 하지만 수학의 근본을 다루던 학자들에게 이런 역설은 치명적이었다.

이렇게 수학의 기초가 역설들 사이에서 흔들리는 시기, 수학의 근본을 다지기 위해 분투하던 새 시대가 열렸다. 많은 수학 관련 학문이 여전히 그때 세워진 체계 위에 서 있다. 그렇게 흔들리는 시기를 겪으면서 수학자들은 자기도 모르게 컴퓨터의 이론을 향해 나아가고 있었다.

그럼 이제 새로운 시대에서 새로운 근본을 견고히 세우고자 했던 학자들과 그걸 뒤집었던 사건들을 알아보자.

완전한 체계를 향한 다른 시도들

논리라는 기반 위에 수학을 쌓아올리려던 프레게, 집합과 무한을 체계화시키려던 칸토어와 같이 수학을 더 단단하고 더 많은 걸 포괄할 수 있는 시스템으로 만들고자 하는 시도는 여럿 있었다. 앞서 언급했듯 이 시기에 수학의 근본을 다루던 수학자들에게는 수학 체계가 흔들리는 것처럼 보였기에 이를 어떻게든 메우고자 한 것이다.

괴델이 불완전성 정리를 증명함으로써 이 모든 시도를 쳐부수기 전까지 이는 계속되었다. 그 중에서 다른 내용과의 연관성이 있다고 판단되는 몇 가지를 소개한다. 노이만, 비트겐슈타인 등 쟁쟁한 학자들의 시도나 오늘날에도 수학의 기초를 이루고 있는 ZFC 공리계 등도 언급할 수 있겠지만 그러면 컴퓨터의 흐름에서 너무 벗어나는 듯 해 생략하며 필요하다면 해당 키워드를 검색해보면 좋을 것 같다.⁶

러셀

"라이프니츠의 초상화를 한번 봅시다! 나도 이 사람과 똑같은 꿈을 꾸었습니다. 논리학 문제에서 인간사에 이르기까지 모든 문제를 푸는 완벽히 논리적인 방법을 발견하겠다는 꿈!"

아포스톨로스 독시아디스, "로지코믹스", 299p 버트런드 러셀의 대사

러셀의 역설은 프레게와 칸토어가 세우려 했던 체계의 제국을 무너뜨렸다. 하지만 러셀(Bertrand Russell) 또한 역설이 없는 논리학을 이용해 수학을 지탱하려고 했던 사람들 중 하나였다. 그는 스스로 제시한 역설을 해결하기 위해 유형 이론을 제안하기도 했다.

또한 화이트헤드(Alfred North Whitehead)와 함께 수학의 기초를 세우기 위한 작업들을 오랫동안 진행한다. 그렇게 10년이라는 시간을 들여 세 권으로 구성된 "수학 원리"를 출간한다. 꼬마들도 직관적으로 아는 사실을 증명하기 위해 362쪽이라는 분량이 필요할 정도로 철저한 증명들이었다.

이러한 연구가 그다지 널리 지지받지는 못한 걸로 보인다. 러셀과 화이트헤드는 "수학 원리"를 출판해 주겠다는 출판사가 없어 자비로 책을 출간했으며 이를 다 읽은 사람은 저자인 러셀과 화이트헤드를 제외하면 쿠르트 괴델뿐이라는 농담이 있을 정도였다.

하지만 직관적으로는 당연한 사실들을 위해 두꺼운 책을 3권이나 쓸 정도의 집요한 시도는 수학의 기초를 위한 당대의 가장 진지한 노력 중 하나였다. 직관에 기대던 수학자들이 여전히 많던 시대에 이런 시도를 했다는 건 대단한 일이다.

또한 이후 괴델의 불완전성 정리 증명조차도 이 "수학 원리"를 바탕으로 한다는 점에서 기여가 작다고 할 수 없다. 또한 그는 자신의 이름이 붙은 러셀의 역설을 극복하기 위해 여러 이론을 제안하는데 이 또한 이후 컴퓨터 과학에 큰 영향을 미쳤다. 예를 들어 형식적 언어(formal language)와 같은 개념들이 그렇다.

알론조 처치

람다 계산법이라는 언어를 기초로 프로그래밍 언어를 디자인해 가면 든든하다. 그 언어의 표현력이 완전하기 때문이다.

이광근, SNU 4190.310 Programming Languages Lecture Notes, 125쪽

프린스턴 대학교의 교수였던 알론조 처치(Alonzo Church)또한 수학의 기초를 세우기 위해 람다 계산법(Lambda Calculus)이라는 새로운 언어를 제안했다. 처치는 함수 그 자체를 수학의 기초로 삼고자 했다. 함수를 통한다면 기존의 집합을 이용한 방식보다 훨씬 간단하고 역설도 피할 수 있을 거라고 생각했다.

예를 들어 $x$를 받아서 1을 더하는 함수 $f(x)=x+1$이 있다고 하자. 이를 람다 계산법으로 표기하면 $f=\lambda x.x+1$로 표현할 수 있다. 이때 $x$는 함수의 인자이므로 $x$를 다른 기호로 바꿔도 상관없다. 람다 계산법을 자세히 다루는 것이 아니므로 여기서는 이 정도로 넘어가자. 필요하다면 내가 쓴 다른 글의 람다 계산법에 대한 간략한 소개를 참고하면 좋겠다.

아무튼 처치는 이런 람다 계산법을 사용해 수학의 근본에 대한 완전한 논리 체계를 구성했다. 그는 람다 계산법을 이용하면 함수를 이용해 훨씬 간단하게 수학의 기초를 세울 수 있다고 생각했고 러셀의 역설 또한 피할 수 있을 거라고 믿었다.

하지만 처치 자신의 제자였던 클레이니와 로서가 람다 계산법 또한 수학의 완전한 기초가 되기에는 논리적인 결점을 품고 있다는 걸 밝혀냈다. 그러나 처치는 좌절하지 않고 람다 계산법을 좀 더 줄여 수정했으며 함수를 이용한 일관적인 계산 체계를 구성했다.

이는 함수에 관한 탄탄한 계산 이론 기초가 되었으며 훗날 Lisp를 비롯한 함수형 프로그래밍 언어들의 이론적 기반이 되었다.

힐베르트

1928년, 미키 마우스가 세상에 데뷔한 해, 대담한 꿈이 유럽 수학계에 번지고 있었다. 당대 수학계를 이끌던 다비트 힐베르트가 독려한 꿈이었다. (...) 몇 개의 추론 규칙만 가지면 앞으로 수학자들이 증명할 명제들을 모두 술술 찾을 수 있는 게 아닐까?

이광근, "컴퓨터과학이 여는 세계: 세상을 바꾼 컴퓨터, 소프트웨어의 원천 아이디어 그리고 미래", 28p

힐베르트(David Hilbert) 역시 수학의 절대적인 안정성을 꿈꿨던 수학자였다. 힐베르트는 역설들을 극복하고 수학을 몇 개의 공리들만 이용해 그 자체로 완전한 존재로 세울 수 있을 거라 믿었다.

이러한 작업의 일환으로 힐베르트는 유클리드의 고전 기하학에 있었던 허점 몇 개를 메우는 공리들을 보였다. 그가 세운 공리 체계가 일관성을 가지는 것도 증명했다. 그리고 그가 세운 공리들에 모순이 있다면 산술 공리들 또한 모순이 발생함을 보였다.

이제 산술의 공리에 모순이 없음을 보이기만 하면 모든 것의 완성이었다. 힐베르트는 1900년 열렸던 세계 수학자 대회에서 20세기 수학계에 던지는 23가지 문제를 제시했는데 그 중 두 번째가 바로 이것, 산술 공리의 무모순성을 보이는 거였다.

그러면서 수학을 그 자체로 완벽한 체계로 세우고자 했으며 이를 위해 수학 시스템이 충족해야 할 조건으로 다음 세 가지를 제시했다.

• 일관성: 모순이 없어야 한다. 어떤 명제와 그 부정을 동시에 증명할 수는 없다.
• 완전성: 모든 명제는 체계 안에서 참 혹은 거짓으로 증명할 수 있다.
• 결정성: 명제를 증명할 수 있는 일반적인 과정이 있다.

그리고 이 세 가지를 충족하는 어떤 구조를 찾아내길 바랐다. 하지만 힐베르트의 위대한 꿈은 오래가지 못했다. 이제부터 살펴볼 괴델이, 러셀의 "수학 원리"를 유일하게 다 읽은 사람이라는 말이 있었으며 역시 수학의 근본에 관심이 많았던 쿠르트 괴델이 힐베르트의 꿈을 산산조각 내버렸다.

모든 꿈이 끝나다

그리고 괴델과 튜링이 이 모든 꿈을 완전히 부쉈다.

괴델의 불완전성 정리

만약 X가 참이라고 증명해주면서 동시에 X가 거짓이라고 증명해주는 시스템이 있다면, 그건 결국 아무거나 다 증명할 수 있다는 얘기가 됩니다. 그럼 우리 수학자들은 도대체 뭐가 됩니까?

폴 호프만 지음, 신현용 옮김, "우리 수학자 모두는 약간 미친 겁니다", 298p

1906년 오스트리아-헝가리 제국의 브르노에서 쿠르트 괴델(Kurt Godel)이 태어났다. 이후 그는 빈 대학교에 진학하여 물리학을 전공한다. 그러다가 수 이론 강의를 듣고 정수론에 매료되어 수학이 자신의 사명이라고 믿게 되었다.

훌륭한 박사 학위 논문⁷을 제출한 후 계속 수학을 연구하던 괴델은 1931년 "수학 원리와 그에 관련된 체계에서 결정불가능 명제들에 관하여"라는 논문을 발표한다. 이 논문에서 그는 수학의 기초를 세우려는 모든 시도를 무너뜨리는 불완전성 정리를 증명했다.

당시 수학의 기초를 탄탄히 세우려는 시도들은 수학이 그 자체로 완전함을 증명하고자 했다. 그러니까 그 체계 내의 모든 명제를 체계 내에서 증명할 수 있다는 것이다. 따라서 순환 논증의 오류 없이 어떻게 이를 해결할 수 있는지가 중요한 문제였다.

하지만 괴델의 논문은 이게 원천적으로 불가능하다는 걸 보였다. 어떤 논리 체계를 세우더라도 체계 내에서 참이지만 또한 체계 내의 규칙으로 증명할 수 없는 명제가 존재한다는 것이다.

다른 글에서 더욱 자세히 다루겠지만 이는 다음과 같은 논리를 통해서이다. 체계 내에서 다음과 같이 정의된 명제를 생각해보자. 이때 증명할 수 있다는 건 체계 내의 공리들로부터 유도될 수 있다는 뜻이고 즉 참이라고 하자.

$U$: $U$는 체계 내에서 증명할 수 없는 명제이다.

$U$는 항상 참이다. 만약 $U$가 거짓이라고 가정해보자. 그러면 $U$가 증명이 불가능하다고 하는 건 거짓이므로 $U$는 증명이 가능하다. 따라서 $U$는 참인데 이는 가정과 모순이다. 따라서 $U$는 참이다. 이 말은 $U$는 체계 내에서 증명할 수 없다는 뜻이다. 이렇게 체계 외부에서 보면 분명히 참인데 체계 내에서는 증명할 수 없는 명제가 존재하므로 힐베르트가 꿈꾼 세 가지 중 완전성이 불가능해졌다.

그리고 $U$의 부정 $\neg U$를 생각해보자. $\neg U$는 자기 자신, 즉 $\neg U$를 증명할 수 있다는 명제이다. 그런데 우리는 앞서 $U$가 참이라고 보았으므로 $\neg U$는 거짓이다. 즉 $\neg U$를 증명할 수 있다는 명제는 거짓이고 따라서 $\neg U$도 증명 불가능하다. $U$도 증명 불가능하고 $\neg U$도 증명 불가능하므로 일관성 또한 불가능해졌다.

그리고 괴델은 만약 어떤 논리 체계가 일관성이 있다면 무조건 $U$와 같은 명제가 존재할 수밖에 없다는 것까지 증명하여 논리주의자들의 퇴로까지 차단했다. 그렇게 수학을 그 자체로 완전한 닫힌 세계로 만들고자 한 꿈은 끝났다. 우리가 만든 체계로는 결코 체계 내의 모든 진실을 말할 수 없다.

수학의 균열에서 태어난 튜링 기계

튜링 기계는 원칙상 기호 형태로 제시되는 모든 수학적 문제를 풀 수 있다. 그 영국 작자는 인간 정신의 내부 상태와 기호 조작 능력을 용케 복제해냈다. 다만 종이 위에다.

벵하민 라바투트 지음, 송예슬 옮김, "매니악", 188p

괴델의 불완전성 정리는 당시 수학계를 완전히 뒤집어 놓았다. 괴델의 증명을 재확인하고 퍼뜨리는 분위기가 학계를 뒤덮고 있었다. 1935년 케임브리지 대학교에서 맥스 뉴먼(Max Newman) 교수가 주최한 강의도 마찬가지였다. 괴델의 불완전성 정리 증명을 리뷰하는 그 강의에 케임브리지를 막 졸업한 앨런 튜링(Alan Turing)도 앉아 있었다.

튜링은 뉴먼 교수의 강의를 듣고 불완전성 정리를 다시 증명하고 또한 보강할 수 있으리라는 생각을 한다. 왜냐 하면 앞서 언급한 힐베르트의 세 가지 조건 중 결정성이 불가능하다는 건 아직 증명되지 않았기 때문이다.

이 결정성에 관한 건 전제와 결론이 모두 적절한 형식으로 주어졌을 때 결론의 참과 거짓을 판단할 수 있는 계산 가능한 절차가 존재하는지에 대한 거였다. 좀 더 구체적으로는 1차 논리로 주어진 정규식에 대해, 한정된 수의 계산만을 거쳐서 해당 정규식이 나타내는 명제가 참인지 판단할 수 있는 알고리즘이 존재하는지였다.⁸

즉 모든 추론을 대체할 수 있는 기계적인 알고리즘을 찾아낼 수 있는지였다! 이건 "힐베르트의 결정 문제"라고 불렸다. 괴델의 증명 이후 이런 알고리즘이 존재한다고 생각하기는 어려웠다. 그렇지만 이런 알고리즘이 존재하지 않는다는 게 증명된 건 아니었다.

그리고 튜링은 1936년 "계산가능한 수에 대해서, 수리명제 자동생성 문제에 응용하면서(On Computable Numbers, with an Application to the Entscheidungsproblem)"라는 논문을 발표한다. 이 논문이 바로, 힐베르트의 결정 문제의 해답이 될 일반적인 알고리즘은 존재할 수 없다는 내용이었다.

튜링 기계의 개념

특별하게 고안된 이론적인 계산 기계는 모든 종류의 일을 할 수 있다고 증명할 수 있다. 사실상 이 기계가 어떤 기계라도 흉내낼 수 있다. 이 특별한 기계를 '범용 기계'라 부를 수 있겠다.

앨런 튜링, 1947년, 런던 수학 협회의 연설에서

앞서 제목을 소개한 논문에서 튜링은 오늘날 우리가 쓰는 컴퓨터의 이론적 원형이 되는 "튜링 기계"라는 개념을 제안한다.

튜링은 먼저 간단한 기계 부품들을 정의하고 이걸로 인간이 종이에 기호를 쓰고 계산하는 모든 과정을 흉내낼 수 있다는 걸 보인다. 튜링이 제시한 튜링 기계의 구성 요소는 다음과 같았다.

• 무한히 긴 테이프: 기호(종류는 유한 갯수)가 쓰여 있고 한 칸 단위로 왔다갔다 할 수 있다
• 테이프를 읽거나 쓰는 장치
• 장치의 현재 상태(종류는 유한 갯수)를 나타내는 기호
• 기계의 작동 규칙 표: 현재 상태와 읽은 기호에 따라 다음 상태와 쓸 기호, 테이프를 움직일 방향을 정하는 규칙(5-튜플 식으로 정의)

이렇게 정의된 기계는 작동 규칙표에 적힌 대로 동작한다. 주어진 테이프를 읽고 작동 규칙표에 적힌 대로 이동하고 기호를 쓰고 상태를 바꾼다. 튜링에 의하면 놀랍게도 이것만으로 계산의 모든 과정을 묘사할 수 있다!

그리고 더 놀라운 점은 모든 종류의 튜링 기계 동작을 수행할 수 있는 하나의 범용 튜링 기계를 만들 수 있다는 것이다. 이 범용 튜링 기계는 어떤 튜링 기계의 동작을 설명하는 테이프를 읽고 그 튜링 기계의 동작을 흉내낸다. 이 말은 또한 모든 튜링 기계의 동작을 유한 갯수 종류의 기호들을 테이프에 적는 것만으로 설명할 수 있다는 뜻이다.

즉 튜링 기계에 적힌 기호들은 일종의 프로그래밍 언어와 같았다. 범용 튜링 기계는 테이프의 기호들을 해석하여 특정한 동작을 할 수 있었다. 그리고 튜링은 자신의 원래 목적인 불완전성 정리의 재증명과 보강을 이루어낸다. 모든 계산 동작을 할 수 있는 튜링 기계로도 절대 풀 수 없는 문제가 언제나 존재한다는 걸 보였다.

이 문제가 오늘날 NP-hard 문제의 원조격인 "정지 문제"다. 정지 문제는 튜링 기계가 주어졌을 때 이 기계가 주어진 입력에 대해 정지하는지를 판단할 수 있는 알고리즘이 있는가에 대한 문제다. 이론적인 내용에 치중한 다른 글에서 더 자세히 다루겠지만 튜링은 칸토어의 대각선 논법을 활용해 이 문제를 해결할 수 있는 튜링 기계가 존재하지 않는다는 걸 증명해냈다.

튜링 기계는 모든 알고리즘을 묘사할 수 있지만 정지 문제를 해결할 수는 없으니 모든 수학 문제를 풀 수 있는 일반적인 과정은 존재하지 않았다. 어떤 문제는 구조적으로 애초에 해결할 수 없었다. 이렇게 힐베르트의 마지막 꿈도 무너졌다.

여담이지만 앞 글에서 이야기했던 처치 또한 알고리즘으로 해결 불가능한 문제가 있다는 걸 보였다. 자신이 만든 체계인 람다 계산법을 이용해서였다. 이후 튜링은 처치와 함께 람다 계산법과 튜링 기계가 동치라는 걸 보이고 사실상 둘은 같은 증명을 했다는 걸 보였다. 오늘날 이걸 처치-튜링 논제라고 부른다.

컴퓨터로 가는 길에서

프레게는 논리를 통해 수학을 세우려 했다. 칸토어는 무한을 체계 속으로 끌어들였다. 러셀과 화이트헤드는 역설을 극복하고 모든 수학을 증명 가능한 공리로 환원하려 했다. 처치는 다른 길을 찾으려다 실패했다. 힐베르트는 수학을 그 자체로 완전하게 만들고자 하는 시도를 마지막으로 꿈꿨다. 그리고 괴델이 이 모든 꿈을 부쉈다.

그 자리에서 튜링은 인간의 모든 계산 행위를 단순한 기계의 동작으로 환원할 수 있음을 보였다. 불완전한, 그리고 절대로 완전해질 수 없는 논리 체계였지만 인간이 해온 계산의 모든 걸 담고 있던 그 체계를 하나의 기계에 담았다.

물론 사람들은 튜링보다 훨씬 오래 전부터 계산하는 기계를 꿈꾸고 일부를 실현해 왔다. 하지만 튜링 이전의 사람들은 이러한 기계가 3가지의 서로 다른 요소로 구성되어 있다고 믿었다. 기계, 프로그램, 데이터였다. 최초의 컴퓨터라고 불리고는 하는 에니악(ENIAC)도 케이블 연결을 바꿔 기계 구성을 수정하며 계산을 수행했다.

튜링이 드디어 이러한 구분을 없앴다. 이 모든 건 사실 하나로 통합될 수 있었다. 튜링 기계에서는 기계의 동작도, 프로그램도 입력되는 데이터도 기호들로 이루어진 테이프 위에 있었다. 오늘날 우리가 코드 자체도 파일로 저장하듯이 프로그램은 데이터가 되었고 데이터는 또한 프로그램이 될 수 있었다.

이 통합을 이루어낸 범용 기계는 컴퓨터의 이론적 기초가 된다. 하지만 이 모든 건 아직 이론이었다. 무한한 길이의 테이프 같은 건 현실에 없었다. 고작 한 칸의 상태만 저장할 수 있는 기계란 큰 의미가 없었다.

컴퓨터를 현실에 만들어내는 도전은 우리가 지금까지 이야기한 이론들과 기계 장치 발전이 얽혀서 일어난다. 새로운 도구들이 필요했다. 그러니까 이제, 튜링의 머릿속 이론을 만들어내기 위해 필요했던 도구들의 발전을 알아보자.

참고문헌

일반적인 컴퓨터공학 전공수업에서 다루는 지식들도 조사한 내용을 이해하는 데 많은 도움이 되었다.

도서

마틴 데이비스 지음, 박상민 옮김, "오늘날 우리는 컴퓨터라 부른다", 인사이트

이광근 지음, "컴퓨터과학이 여는 세계: 세상을 바꾼 컴퓨터, 소프트웨어의 원천 아이디어 그리고 미래", 인사이트

카와조에 아이 지음, 이영희 옮김, "컴퓨터는 어떻게 만들어졌나요?", 로드북

아포스톨로스 독시아디스, 크리스토스 H. 파파디미트리우 글, 알레코스 파파다토스, 애니 디 도나 그림, 전대호 옮김, "로지코믹스", 알에이치코리아

더멋 튜링 지음, 김의석 옮김, "계산기는 어떻게 인공지능이 되었을까?", 한빛미디어

알렉산더 R. 갤러웨이 지음, 이나원 옮김, "계산할 수 없는: 장기 디지털 시대의 유희와 정치", 장미와동백

앤서니 케니 지음, 김영건 외 옮김, "서양 철학사", 이제이북스

위키피디아 문서

• Logicism
• NP-hardness
• Russell's paradox

기타 자료

Jeffrey Kaplan 유튜브, Russell's Paradox - a simple explanation of a profound problem

https://www.youtube.com/watch?v=ymGt7I4Yn3k

Contemporary Logic Part 1: Frege’s Revolution

https://www.youtube.com/watch?v=9WvIc4AwL6o

Contemporary Logic Part 2: Current Systems and Methods

https://www.youtube.com/watch?v=pQO1t2Y627Y

Stanford Encyclopedia of Philosophy, Frege’s Logic

https://plato.stanford.edu/entries/frege-logic/

Stanford Encyclopedia of Philosophy, Russell's Paradox

https://plato.stanford.edu/entries/russell-paradox/

Footnotes

1. 마틴 데이비스 지음, 박상민 옮김, "오늘날 우리는 컴퓨터라 부른다", 50p에서 따왔다. ↩

2. 프레게는 은퇴할 때까지 부교수였다. 동료들이 그의 연구의 가치를 인정하지 않았기 때문에 정교수로는 승진하지 못했다. ↩

3. 단 이 글에서 사용하는 기호들이 프레게가 소개한 것과 같은 모양은 아니다. 프레게는 같은 의미를 가진 기호들을 제시했으나 오늘날 많이 사용되는 건 이탈리아의 논리학자 주세페 페아노의 기호이다. 페아노의 기호 쪽이 타자기로 치기도 쉬웠으며 버트런드 러셀이 이를 사용하면서 유명해졌다. 기호가 어떤 모양인지 중요한 건 아니기 때문에 이 글에서도 대중적으로 쓰이는 페아노의 기호를 사용한다. ↩

4. 알렉산더 R. 갤러웨이 지음, 이나원 옮김, "계산할 수 없는: 장기 디지털 시대의 유희와 정치", 장미와동백, 193p에서 재인용 ↩

5. 흥미가 있다면 칸토어 역설, 부랄리포르티 역설, 클레이니-로서 역설 등을 참고 ↩

6. Stanford Encyclopedia of Philosophy, "Russell's Paradox" 문서 혹은 체르멜로-프렝켈 집합론, ZFC 공리계에 관한 수학사를 참고할 수 있다. ↩

7. 괴델이 박사 학위 논문을 통해 증명한 내용은 "완전성 정리"라고 불린다. ↩

8. 마틴 데이비스 지음, 박상민 옮김, "오늘날 우리는 컴퓨터라 부른다", 144-146p, 219-221p 참고 ↩