컴퓨터 과학의 역사를 거슬러 올라가다보면, 수학이 근본적인 위기를 맞이했던 시대를 만나게 됩니다. 그 위기는 이런 질문으로 시작합니다.

이발사의 역설Barber paradox이라고 부르는 이 문제는 두 결론 중 어느 한쪽을 가정해보더라도 모순이 나타납니다. 이것이 의미하는 바는 단순한 연역법deduction으로도 수학의 기반인 논리학을 흔들 수 있다는 것입니다.

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

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

앞으로의 내용을 통해, 힐베르트가 요구한 것이 구체적으로 무엇이었고, 그 이유가 무엇인지, 그리고 이로부터 어떻게 컴퓨터가 나올 수 있었는지 그 역사를 최대한 간략하게 훑어보겠습니다.

자기 자신을 언급하는 문제

앞서 언급한 이발사의 역설과 비슷하게, 논리적인 방법만을 거쳐서 모순을 다시 한번 이끌어내보겠습니다. 하지만 이번에는 좀 더 수학의 언어에 가깝게 해볼 것입니다. 바로 자기 자신을 원소로 갖지 않는 집합set을 떠올려보는 것입니다. 그러면 이 집합은 자기 자신을 갖고 있을까요? (한번 풀어보세요.)

답은 ‘둘다 아니다’가 됩니다. 어느 쪽을 가정하든, 그 반대 쪽 또한 동시에 참이 되기 때문입니다.

$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라고 하는 가상의 기계와 사실상 같은 개념입니다.

알고보면 이런 것들은 프로그래밍을 할 때 은연중에 많이 사용하고 있는 것입니다. 예를 들어 유한 상태 기계는 정규 표현식을 처리할 때, 푸시다운 오토마타는 컴파일러가 프로그래밍 언어를 파싱할 때 쓰이곤 합니다.

레퍼런스

• 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)