컴퓨터 과학의 역사를 거슬러 올라가다보면 수학이 근본적인 위기를 맞이했던 시대를 만나게 됩니다. 그 위기의 시작은 이런 질문의 모습을 하고 있는데요.

”스스로 면도하지 않는 사람만 면도하는 사람이 있습니다. 이 사람은 자신의 수염을 면도할까요?”

두 결론 중 어느 한쪽을 가정해보더라도 모순을 만나게 되는데요. 이발사의 역설Barber paradox이라고 불리는 이 문제는 단순한 연역법deduction으로 수학의 기반인 논리학을 흔들 수 있음을 보였습니다.

20세기 초기 당시, 힐베르트David Hilbert는 이런 모순을 수학에서 걷어내고 싶었습니다. 그리고 그가 생각하기에 이상적인 수학의 모습을 제시했는데요. 수학이 실제로 그런 모습이라고 증명이 이루어지길 바랐습니다.

하지만 어떤 세 명의 인물이 차례로 그 반대의 것, 다시 말해 수학이 무엇을 할 수 없는지를 보였습니다. 그 인물은 쿠르트 괴델Kurt Gödel, 앨런 튜링Alan Turing, 그리고 알론조 처치Alonzo Church입니다. 그런데 역설적이게도 그 과정에서 반대로 우리가 무엇을 기계적으로mechanically 할 수 있는지 보게 됩니다. 그리고 이것이 현대 컴퓨터의 개념적인 모델로 발전하게 됩니다.

힐베르트가 구체적으로 무엇을 요구했고, 왜 그랬던 것인지, 그리고 이로부터 어떻게 컴퓨터가 나올 수 있었는지 복잡한 디테일은 생략하고 그 역사를 훑어보겠습니다.

자기 자신을 언급하는 문제

논리적인 방법만을 거쳐서 모순을 이끌어낼 수 있다면 어떨까요? 앞서 언급했던 이발사의 역설이 그런 문제인데요. 비슷하지만 좀 더 수학에 직접적으로 관련된 것을 만들 수 있습니다. 바로 자기 자신을 원소로 갖지 않는 집합set이 그런 것입니다. 그러면 이 집합은 자기 자신을 갖고 있을까요?

즉 집합 $A = \{ x : x \notin x \}$가 있을 때, $A \in A$인지 $A \notin A$인지 결정할 수 있느냐 인데요. 어느 쪽을 가정하든, 그 반대 쪽 또한 동시에 참이 됩니다.

$A \in A$라고 해봅시다. 그러면, $A$는 $A$의 원소가 될 조건 $x \notin x$를 만족시켜야 하므로, $A \notin A$가 되어 모순을 만들게 됩니다. 반대쪽, 즉 $A \notin A$을 가정했을 경우도 쉽게 해볼 수 있습니다.

수학에서 기초적으로 쓰이는 집합 개념과 논리학만 가지고도 이 모순을 만들어낼 수 있었는데요. 러셀의 패러독스Russell’s paradox이라고 불리는 이것은 수학에 근본적인 위협이 됐습니다. 그래서 당시 20세기 초는 집합과 논리에 대해 다시 생각해봐야 할 때였습니다.

바닥부터 다시 짓기

무엇이 잘못일까요? ‘스스로’나 ‘자기 자신’ 같은 단어를 쓰면서 자기 언급을 하는 문장이 문제가 아닐까요? 그래서 이런 문장을 만들어내는 것을 처음부터 금지하면 문제가 해결되지 않을까요?

당시 러셀Bertrand Russell과 화이트헤드Alfred Whitehead는 논리적인 규칙을 완전히 처음부터 다시 만들어냈습니다. 정말 당연해보이는 것조차 분명하게 적으면서요. 물론 여기에 ‘자기 자신’ 따위를 언급을 할 수 있다는 규칙은 없었습니다. 그리고 그런 규칙을 사용하는 수학에 모순이 끼어들 틈이 없기를 바랐습니다.

그리고 그렇게 만든 논리 규칙이 수학에 적용시킬 수 있을 만큼 충분히 쓸만하다는 것도 보였습니다. $1 + 1 = 2$ 임을 이끌어내면서요. 그리고 이 결과를 수학 원리Principia Mathematica라는 책으로 내게 됩니다. ($1+1=2$임을 증명한 책으로 알려져 있지만, 그보다는 그것을 이끌어낼 수 있는 논리 체계를 만들어냈다고 하는 것이 정확할 것입니다.)

피할 수 없는 자기 언급

이 책의 내용을 그대로 이용해서 어떤 결과를 발표한 괴델이라는 사람이 있었는데요. 그는 사실 이런 논리 체계 또한 불가피하게 자기 언급 문장이 만들어지는 것을 막을 수 없다는 것을 보였습니다.

”이 문장은 증명할 수 없다.” 이 문장은 괴델이 실제로 만들어낸 문장입니다. 그런데 실제로 증명할 수 없다면 맞는 말이 될 텐데요. 하지만 그렇기 때문에 그게 맞는 말인지는 증명할 수 없게 됩니다. 즉 맞는 말이긴 한데 증명할 수 없는 사실이 수학에 존재하게 됩니다.

더 나아가, 사실은 러셀과 화이트헤드가 만들어낸 논리 체계뿐만 아니라, $1+1=2$를 이끌어 낼 수 있는 그 어떤 논리 체계에서도 그렇다는 것을 보이게 됩니다. 이는 괴델의 불완전성 정리Gödel’s incompleteness theorems라는 이름으로 남게 됩니다. (왜 이것이 불완전성인지는 곧 볼 것입니다.)

존재의 의미

괴델은 왜 그런 문장을 굳이 직접 만들었을까요?

당시 수학자들 중에 직관주의intuitionism를 따르는 사람들은 실제로 만들어 낼 수 없으면 존재가 증명되지 않았다고 믿었습니다. 존재란 실제로 만들어냈거나, 그런 방법을 제시했을 때 입증된 것이라고 보았기 때문인데요.

그래서 논리 규칙 중에 배중률law of excluded middle, 즉 어떤 문장도 맞거나 틀릴 뿐 그 중간은 없다고 배척한다는 원리는 유효한게 아니라고 보았습니다. 다시 말해, 어떤 것이 존재하지 않는다고 가정한 것이 모순을 낳는다고 해서, 그것이 존재한다고는 생각하지 않았습니다. 직접 만들어 낸 것이 없으니까요.

정리하면 직관주의는 존재의 증명이 구성적constructive이어야 한다고 요구했습니다. (말 그대로, 구성해내야 하니까요.) 그래서 괴델은 자기 언급 문장을 직접 만들어내며, 1931년 논문에 “직관주의적으로 반박할 수 없는 방식in an intuitionistically unobjectionable manner으로 증명했다.” 라는 문구를 더했습니다.

한편, 힐베르트 주변에서 이 직관주의를 따르는 사람들이 생기기 시작했습니다. 하지만 힐베르트는 직관주의를 따르고 싶지 않았는데요. 수학에 대한 위협이라고 생각했기 때문입니다.

이후 힐베르트가 이상적인 수학의 모습을 만들어내기 위해 힐베르트 프로그램Hilbert’s program이라는 이름으로 그 과제를 시작했을 때, 직관주의자들 또한 승복할 수 있도록 만들어야 했습니다. 그리고 그런 결과 중 하나가 괴델의 작업이었습니다.

이상적인 수학의 모습

힐베르트는 어려운 문제를 제시하는 것이 곧 수학의 발전을 이끈다고 믿었습니다. 그래서 1900년에 이르렀을 때 소위 힐베르트 문제Hilbert’s problems라고 부르는 것을 발표했는데요. 그 두 번째 문제는 산술 체계의 무모순성 증명, 즉 수학 체계에 모순이 없음을 증명하는 일이었습니다.

왜냐면 일년 전에 기하학의 원리Foundations of Geometry라는 책을 내면서, 기하학의 무모순성이 결국에는 산술 체계의 무모순성에 달려있다고 보였거든요. 그리고 남은 과제로서 두 번째 문제를 고른 것이었습니다.

이후 1928년 국제 수학자 대회International Congress of Mathematicians에서 힐베르트는 목표를 좀 더 구체적으로 다듬었습니다. 힐베르트가 제시한 세 가지 과제는 이런 것이었는데요. 수학이 ‘완전complete’한 지, ‘무모순적consistent’인지, 그리고 ‘결정가능decidable’한 지였습니다.

각각은 이런 의미가 있습니다. ‘완전’하다는 것은, 모든 문장은 맞거나 틀리다고 증명될 수 있어야 한다는 뜻입니다. 그러니까 $1+1=2$이든 $1+1=3$이든, 만들어낼 수 있는 모든 문장이 맞는지 틀린지 수학은 말할 수 있어야 합니다.

‘무모순적’이란, 논리적인 단계만 거쳤다면 모순이 없음이 보장되어야 한다는 의미입니다. 예를 들어, 제시된 논리 규칙만 따랐는데, $1+1=2$가 맞으면서 동시에 틀린 문장이 되어선 안됐습니다. 생각해보면 당연히 수학이 가져야할 성질입니다.

마지막으로 ‘결정가능’한 것이란, 어떤 문장에 대해서든 그것이 맞는지 틀린지 결정할 수 있는 절차가 있다는 것입니다. 즉 결과 뿐만 아니라, 그 결과를 이끌어낼 수 있는 단계도 수학은 말할 수 있어야 합니다.

이렇게 힐베르트가 제시한 성질을 증명한다면, 수학은 모순이 없고, 맞는 문장은 항상 증명할 수 있는 그런 학문이 되는데요. 게다가 어떤 문장이든 결정가능하기 때문에, 맞는지 틀린지 그저 기계적으로 알아낼 수 있게 됩니다. 즉 증명 기계같은 것이 세상에 나올 수 있게 됩니다. (이렇게 수학자들은 직업을 잃을 뻔했습니다.)

수학의 한계에서 잃은 것과 얻은 것

그런데 얼마 지나지 않아, 앞서 살펴본 것처럼, 괴델은 수학이 ‘완전’하지 않다는 것을 보이게 됩니다. 즉 맞는지 틀린지 증명할 수 없는 문장을 직접 만들어냅니다. (그래서 괴델의 작업에 불완전성 정리라는 이름이 붙었습니다.)

덧붙여 “수학은 무모순적이다” 라는 문장도 바로 그런 문장이라는 것을 보이게 되는데요. 다시 말해 수학 그 자체로는 그 수학에 모순이 없다고 증명할 수 없다는 것을 보이게 됩니다. 이렇게 첫 번째와 두 번째 문제에 괴델은 부정적인 답을 하게 됩니다.

마지막으로 남은 세 번째는 소위 결정문제Entscheidungsproblem라는 이름을 갖고 있는데요. 이 문제의 답은 앨런 튜링와 알론조 처치가 각자 다른 방법으로 보이게 됩니다. 모든 문장에 참인지 거짓인지를 결정하는 절차는 없다는 것을요. (이렇게 수학자들은 직업을 지켰습니다.)

그 과정에서 튜링은 오늘날 튜링 머신Turing machine이라고 하는 개념적인 기계를 떠올렸습니다. 특히 튜링은 정지 문제halting problem라고 이름 붙인 그 문제가, 결정 절차를 알아낼 수 없는 바로 그것임을 보였습니다. 그러니까 오늘날 컴퓨터의 개념적인 모델이 된 튜링 머신은, 사실 무엇을 할 수 없는지 보이기 위해 고안한 장치였습니다.

하지만 한 쪽을 결정하는 경계선이 반대쪽도 결정하는 것처럼, 이 튜링 머신을 통해 계산 가능computable한 것이 무엇인지 생각해볼 수 있게 되었습니다. 이렇게 튜링 머신으로 할 수 있는 일을, 그리고 그것만을 알고리즘algorithm이라고 부르게 되었습니다. 튜링 머신이 할 수 있는 것과 계산 가능한 것은 동일하다는 명제는, 컴퓨터 과학의 근본적인 가정인 처치-튜링 명제Church-Turing thesis으로 남게 되었습니다.

숫자로서의 컴퓨터

1940년대에 최초의 컴퓨터라고 알려진 에니악ENIAC이 만들어졌을 때에도, 프로그램과 데이터는 별개의 것으로 디자인 됐는데요. 프로그램은 외부에서 배선판의 수많은 선을 다시 꽂는 것으로 준비해야 했습니다.

한편, 튜링이 논문에서 생각했던 트릭은 다른 튜링 머신을 따라하는 튜링 머신을 만들어낸 것이었습니다. 이는 보편 튜링 머신universal Turing machine이라고 불리는데요.

각 튜링 머신에는 고유한 숫자를 적절히 부여할 수 있었습니다. 튜링이 부르길 디스크립션 넘버description number라고 하는 것을요. 그 숫자에 그 튜링 머신이 하는 일을 인코딩할 수 있었습니다. (그래서 설명하는describe 숫자입니다.) 덕분에 보편 튜링 머신은 그 숫자를 읽어 그 튜링 머신이 하는 것을 똑같이 시뮬레이션 할 수 있었습니다.

그런데 이 관점에서는 어떤 프로그램을 수행하는 튜링 머신이라도, 결국 보편 튜링 머신 입장에서는 읽어야할 데이터가 됩니다. 그러면 프로그램 또한 데이터로서 바라볼 수 있게 됩니다.

현대의 컴퓨터와 비교해보세요. 프로그래머가 명령을 작성하면, 컴파일러라는 프로그램은 그것을 받아 하나의 거대한 숫자로 변환합니다. 그리고 컴퓨터는 그 숫자를 읽고, 작성했던 명령을 수행합니다. 여기서 이 숫자는 곧 디스크립션 넘버로, 그리고 컴퓨터는 보편 튜링 머신으로 생각해볼 수 있습니다. 오늘날 컴퓨터를 보편 튜링 머신의 구현으로 볼 수 있는 이유입니다.

실제로 만들기

튜링 머신은 힐베르트의 결정 문제를 풀기 위해 생각해냈던 추상적인 개념이었지만, 곧 현실에서 만들어보려는 시도가 나타났는데요. 폰 노이만John von Neumann은 이를 현실에서 만들어보려고 했습니다.

에니악 제작에 참여했던 폰 노이만은 다음에 만들 에드박EDVAC이라는 컴퓨터로 관심을 옮겼는데요. 에드박의 첫 번째 초안에서 보편 튜링 머신의 물리적인 모형으로 만들 것을 제안했습니다. 즉 데이터와 명령을 모두 담는, 폰 노이만이 부르길 메모리라는 것을 더하는 것을요. 이 디자인은 폰 노이만 아키텍처von Neumann architecture라는 이름으로 남게 됩니다.

무의미한 기호 조작

시간을 되돌려 덧붙일 이야기가 있습니다.

힐베르트는 수학적인 문장 그 자체에는 아무런 의미가 없다고 보았습니다. 점, 선, 면이라는 단어를 책상, 의자, 맥주컵으로 바꿔치더라도, 바로 그 책상, 의자, 맥주컵이 기존에 점, 선, 면이 따르던 규칙을 따르기만 하면 아무 문제가 없다고 생각했는데요.

예를 들어 ‘선에는 무한히 많은 점이 있다.’라는 문장을, ‘의자에는 무한히 많은 책상이 있다.’라고 고쳐쓰는 것처럼요. 왜냐면 사실 점, 선, 면 같은 것은 즉 무정의 용어undefined term로 남겨뒀거든요. 그래서 실제로 무엇을 가리키는 지는 신경쓰지 않았습니다.

그런데 이런 식으로 생각하면, 수학이란 단순히 $1+1+1$ 같은 기호들의 나열에서 적절한 규칙을 따라 조작해 $2+1$ 같은 또 다른 기호들의 나열을 만들어내는, 즉 기호 조작의 학문으로 볼 수 있습니다. 그 기호가 실제로 무엇을 가리키는 지는 신경쓰지 않고요. 이런 관점을 형식주의formalism라고 불렀는데요. 힐베르트는 이를 대표하는 인물이었습니다.

형식주의는 이렇게 본질적으로 무의미한 체계를 만들었습니다. 시작점이 되는 문장들을 공리axioms라는 이름으로 선택하고, 문장의 조작 규칙을 추론 규칙inference rule이라는 이름으로 만들었습니다. 이렇게 규칙에 따라 조작한 결과를 모아 정리theorem라고 불렀습니다. 그러면 수학에서 정리를 이끌어낸다는 것은, 그저 기호를 잘 조작하는 행위에 불과하게 됩니다.

무엇인지 모르고 하는 계산

기호 조작은 먼저 조작할 기호가 필요합니다. 그런 기호들을 모아 형식 언어formal language라고 불리는 인공적인 언어를 만들 수 있는데요. 이런 형식 언어는 원하는 대로 만들어낼 수 있습니다.

대표적으로 정규 언어regular language, 문맥 자유 언어context-free language 같은 것이 있습니다. 이 두 형식 언어는 각각 유한 상태 기계finite-state machine와 푸시다운 오토마타pushdown automata라고 하는 개념적인 기계와 사실상 같은 개념인데요. 즉 의미를 제거한 언어로부터, 그 언어를 이해하는 개념적인 기계가 존재합니다. 이것은 이미 우리가 많이 사용하고 있습니다. 예를 들어 유한 상태 기계는 정규 표현식을 처리하는 데 쓸 수 있고요. 푸시다운 오토마타는 컴파일러가 프로그래밍 언어를 파싱하는 데 쓸 수 있습니다.

마치며

오늘날의 컴퓨터가 탄생하기까지의 역사를 살펴보았습니다. 컴퓨터의 개념적인 모델이 수학과 논리학에서 나타나기 시작했는데요. 그래서 이들 사이에는 밀접한 관련이 있을 수밖에 없습니다.

특히 논리학은 컴퓨터의 개념적인 모델과 연관이 있고, 뿐만 아니라 실제 컴퓨터를 구현할 때 논리 게이트logic gate를 만드는 단계부터 필요하게 됩니다. 사실 그 구현에서 쓰이는 논리학은 기존의 아리스토텔레스Artistotle가 정리했던 논리학 대신에, 하나의 대수algebra 체계로 추상화한 불 논리Boolean logic가 쓰입니다. 이는 프로그래밍에서 쓰는 논리 연산, 즉 and와 or 에서도 나타납니다.

튜링이 결정 문제를 풀기 전에, 사실 처치는 똑같은 것을 람다 캘큘러스lambda calculus라고 하는 것을 만들어 증명했는데요. 이는 오늘날 프로그래밍의 람다 표현식lambda expression에 영향을 끼치게 됩니다.

못다한 부분들

중간에 생략했지만 관심이 없다면 볼 필요 없는 내용은 이런 것이 있습니다.

튜링 머신은 계산 모델model of computation, 즉 개념적인 계산 기계라고 불리는데요. 사실 괴델 또한 그의 논문에서, 오늘날 프리미티브 리커시브primitive recursive라고 부르는, 반복적인 계산 절차를 담은 함수를 만들었습니다. 그리고 이를 확장한 제너럴 리커시브general recursive, 또는 뮤 리커시브μ-recursive라고 불리는 함수는 튜링 머신과 할 수 있는 일이 같은데요. 그러니 괴델과 튜링, 처치로 인해, 컴퓨터는 물리적으로 구현되기 전에 이미 세 가지 모습으로 인류의 머리속에 등장하고 있었던 것입니다.

또한 자연수의 개수는 $\aleph_0$로 가장 작은 무한에 해당하는데요. 각 튜링 머신에는 자연수의 디스크립션 넘버가 항상 부여되기 때문에, 세상에는 자연수의 개수만큼 튜링 머신이 존재한다는 것을 알 수 있습니다. 그러면 사람이 생각해 낼 수 있는 일이 자연수보다 더 많이 존재한다면, 벌써부터 튜링 머신은 해낼 수 없는 일이 존재한다는 것을 금방 알 수 있습니다. 그리고 정지 문제가 바로 그런 문제 중 하나가 됩니다.

한편 컴퓨터의 탄생과 더불어, 러셀의 패러독스는 다른 분야에도 영향을 끼쳤는데요. 특히 사람들은 집합과 논리학을 다시 생각할 기회를 가졌습니다.

집합은 이후 공리적인 방법으로 다시 정의해보기 시작했습니다. 다시 말해 무엇을 집합으로 부르고, 또 무엇을 집합으로 부르지 않을 것인지 구분하는 작업이 나타났습니다. 이로부터 각 이론에 공헌한 사람들의 앞글자를 따서, ZF 집합론ZF set theory과 NGB 집합론NGB set theory 같은 이론이 나타나게 되었습니다. 차이가 있다면 NGB 집합론은 집합이라고 부를 수 없는 것을 위해 클래스class라는 개념을 더하고, ZF 집합론은 그런 것을 직접 언급하지는 않는다는 것입니다.

논리학은 일차 논리학first-order logic이 중요한 성과인데요. 여기서는 문장에서 ‘모든’이나 ‘어떤’이라는 단어를 제한된 수준에서만 쓸 수 있습니다. 여기서 설명하는 논리학은 ZF 집합론과 같이 다른 이론에서 쓸 수 있는 논리 체계를 제공하고요. 여기에서 또한 괴델의 불완전성 정리를 이끌어낼 수 있습니다.

레퍼런스

• The Universal Computer (Martin Davis, 2000), 또는 수학자, 컴퓨터를 만들다 (2005):

• Alan Turing (Douglas Hofstadter, 2014), 또는 앨런 튜링의 이미테이션 게임 (2015): 앨런 튜링의 생애를 비롯해, 그가 괴델과 처치로부터 받은 영향과, 튜링 머신의 수학적인 설명을 담고 있습니다.

• Godel: A Life of Logic (Werner DePauli, John Casti, 2000), 또는 괴델 (2002)

• On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (Kurt Gödel, 1931)

• Gödel’s Proof (Ernest Nagel, James Newman, Douglas R. Hofstadter 2008), 또는 괴델의 증명 (2010): 괴델의 불완전성 정리를 이해하기 위해 원래의 논문을 읽는 대신 참고해볼 만 합니다.