[컴퓨터의 기원] 1. 힐베르트 프로그램

1. 힐베르트 프로그램

 1-1. 비유클리드 기하학과 러셀의 역설

  1-1-1. 비유클리드 기하학의 등장

 우리는 초등학교, 중학교 때 배우는 (유클리드) 기하학을 통해 "수학적으로 사고한다"는 것의 진정한 의미를 처음 배운다. 어떤 기하학적 진술이 있고 그것의 참을 증명해나가는 것을 배우는 것이 바로 수학적 사고다.

예를 들어, "삼각형의 내각의 합은 180도이다."라는 진술은 기하학의 공리, 혹은 공리에서 증명된 정리를 활용해 아래처럼 엄밀하게 증명할 수 있다.

삼각형의 내각의 합이 180도인 이유(증명)

 

 이때, 공리란 그 자체로 기하학적 진술(명제)이면서, 동시에 별도의 증명 과정 없이 참이라고 여기는 진술을 말한다. 유클리드 기하학은 아래의 다섯 가지 공리를 바탕으로 논리 추론 규칙을 사용해 수많은 기하학적 진술(명제)들의 참/거짓을 밝혀낸다. 그 수많은 정리들이 고작 5가지 명제로부터 생산되는 것이 놀랍지 않은가! 

1. 서로 다른 두 점이 주어졌을 때, 그 두 점을 잇는 직선을 그을 수 있다.
2. 임의의 선분은 더 연장할 수 있다.
3. 서로 다른 두 점 A, B에 대해, 점 A를 중심으로 하고 선분 AB를 한 반지름으로 하는 원을 그릴 수 있다.
4. 모든 직각은 서로 같다.
5. 임의의 직선이 두 직선과 교차할 때, 교차되는 각의 내각의 합이 두 직각(180도)보다 작을 때, 두 직선을 계속 연장하면 두 각의 합이 두 직각보다 작은 쪽에서 교차한다. (평행선의 공리, 제5공준)

 

 그런데 유클리드는 5번 공리(평행선 공리)가 정말로 공리가 맞는지 확신하지 못했다고 전해진다. 이 공리가 거짓인 명제일까봐 걱정한 것이 아니다. 공리는 별도의 증명 없이 참이라고 받아들이자는 약속이므로 참/거짓 구분이 문제가 되지 않는다. 유클리드가 걱정한 것은, 만약 1~4번 공리를 사용해 5번 명제를 증명할 수 있다면, 굳이 5번 명제를 기본 공리 중 하나로 취급할 이유가 없다는 뜻이다.

 후대의 수학자들에게도 유클리드 기하학의 5번 공리는 마치 다른 공리들로부터 유도되는 어떤 '정리'처럼 보였다. 그러나 수많은 수학자들이 1번에서 4번까지의 공리를 사용해 5번을 이끌어내려고 시도했으나 실패했다.

그래서 또 다른 방식을 사용해 5번 공리가 정말로 공리로서 포함되어야 할 자격이 되는지 증명하고자 귀류법을 사용했다. 귀류법이란 증명하고 싶은 명제가 거짓이라고 가정한 뒤 모순을 이끌어내어 명제가 거짓이 아니라 참임을 증명하는 방법을 말한다. 즉, 5번 공리가 거짓이라고 가정했을 때, 그 기하학 체계에 모순이 생기면 5번 명제는 공리로 포함해야 하는 것이다.

 잠깐 역사적인 이야기를 하자면, 사실 유클리드 후대의 수학자들에게 5번 공리는 언제나 골칫거리였다. 그래서 5번 공리가 들어맞지 않는 독특한 기하학 세계에 대한 아이디어는 이미 많은 수학자들에 의해 단서가 잡히고 있었다. 꽤 오래 전부터 이미 "곡률" 즉, 휘어진 공간에 대한 기하학 아이디어들이 있었던 것이다.

 

위와 같이, 오목하거나 구형의 공간이 바로 유클리드의 5번 공리가 통하지 않는 공간이다. 만약 기하학에 반드시 5번 공리가 포함되어야 할 어떤 이유가 있어야 한다면, 그것은 바로 희한하게 휘어진 저 비유클리드 공간들(각각 타원기하학, 쌍곡선기하학이라 부름)에서의 기하학에 문제가 생기기 때문일 것이다. 5번 공리를 포함하지 않는, 오목하거나 원형의 공간에서 기하학은 성립되지 않으므로 반드시 5번 공리는 공리로서 꼭 존재해야 한다는 논리다. 이것이 귀류법이다.

그러나 문제가 발생했다...

 5번 공리를 부정한 타원기하학, 쌍곡선기하학 모두 1번에서 4번까지의 공리가 통한다는 것이 밝혀진 것이다! 정확하게는 5번 공리를 부정해도 이들 기하학 체계에는 모순이 없다는 것이 증명되었다.

 이로 인해 수학 세계에 빨간불이 켜졌다. 위 그림이 말해주는 5번 평행선 공리는 우리의 경험과 직관에 의해 너무나 자명한 것으로 여겨진다. 한 선에 직각으로 출발해 선 두개를 연장하면 그것은 평행선이며 평행선은 아무리 무한하게 길이를 연장해도 서로 만나지 않는다. 적어도 이 명제는 우리의 경험과 직관에 딱 들어맞는다.

 그런데 이 평행선 공리가 거짓이라고 해도 아무런 문제가 발생하지 않는다고?! 게다가 그런 새로운 기하학도 어느정도 세계와 우주에 유용하게 활용될 수 있다고...? 이 말은 우리가 지금까지 자명하다고 여기고 있는 수많은 공리들이 정말로 참이라고 믿을 근거가 있는지 의문을 자아내게 만든다. 수학의 하부 구조가 흔들리기 시작한 것이다.

 

1-1-2. 논리주의와 러셀의 역설

공리에 대한 믿음이 흔들리기 시작하자 이제 수학자들의 날카로운 비판의 대상은 산술 세계로 넘어간다. 즉, "자연수의 세계" 말이다...!

자연수 체계는 그야말로 우리가 알고 있는 수학의 총체를 지탱하는 핵심적인 하부 구조다. 정수와 유리수, 무리수와 실수는 모두 자연수 체계로부터 이끌어낼 수 있다는 것이 수학자들에 의해 증명되었다. (실제로 우리는 교육과정에서 이 순서대로 수학을 학습해나간다!)

그렇다면 자연수와 사칙연산으로 이루어진 산술 체계에 대한 수학 시스템(페아노 공리라 부름)은 결코 흔들리는 일이 없어야 할 것이다.

하지만 비유클리드 기하학의 충격으로 인해, 이제 수학자들은 자신들의 작업들을 지탱하고 있는 자연수 체계의 공리들에게 의문을 품기 시작했다. 정말로 이 공리들을 참이라고 믿을 수 있을까? 혹시 참이 아니라고 해도 아무런 상관이 없다면 그것은 기하학의 충격보다 더 심각한 일이 아니겠는가. 우리가 이해하고 있는 수에 대한 직관이 틀릴 수도 있다는 것이므로....

결국 수학자들은 자연수의 기초를 튼튼하게 만들기 위해 새로운 작업을 시도한다. 그것이 바로 프레게로 대표되는 논리주의다.

프레게

논리주의란, 산술 체계의 기초를 논리학으로 세우려는 시도를 말한다. 프레게의 제안에 따르면, 우리가 자명하다고 여기는 자연수와 산술은 집합의 성질로 환원될 수 있으며, 따라서 집합론에 기반하고 있는 논리학의 내용으로 자연수 산술 체계의 공리들을 이끌어낼 수 있다고 본 것이다.

이를테면, 자연수 3이란 어떤 집합 {a, b, c}와 일대일로 대응할 수 있는 모든 집합, 예를 들어 {가, 나, 다}, {고양이, 강아지, 토끼}, ... 를 모두 모은 집합이 바로 수 3의 실체인 것이다. 

여기서 중요한 핵심은 논리학(집합론)으로 산술 체계의 공리를 탄탄하게 받쳐줄 수 있다는 믿음은 논리학은 명백한 사실이라는 믿음에 기초하고 있다는 점이다. 지금의 우리에게도 논리학의 다양한 논증 법칙들은 자명한 것으로 받아들이고 있지 않은가. 논리적 추론 과정은 그 자체로 탄탄하기 때문에 산술 체계를 논리학 위에 올려 놓겠다는 시도의 배후에는 논리학(*정확하게는 칸토어의 집합론)에 대한 확신에 근거하고 있는 것이다.

러셀

그러나 칸토어의 집합론(논리학)에도 패러독스(모순)가 있다는 것이 발견되었고, 이를 발견한 사람이 바로 러셀이다.

집합은 구별 가능한 대상들의 집합으로 정의되므로 위와 같이 자기 자신을 포함하지 않는 집합 X를 정의할 수 있다. 그런데 자기 자신을 원소로 가지지 않는 집합 X가 있다면 위 정의에 의해 그 X는 X의 원소가 된다. 이러면 다시, X는 자기 자신을 원소로 가지지 않으므로 조건을 만족해 X의 원소가 된다.... 그렇다.. 모순이다.

논리적 추론과정과 그 정합성은 칸토어의 집합론에 기반하고 있었기 때문에 집합 개념에 대한 논리적 모순은 논리주의에게 큰 충격으로 다가왔다. 자연수 체계의 기초를 다듬으려고 가져온 논리학에도 문제가 있었다고..?!

물론 러셀이 프레게에게 자신의 역설을 제시한 것은 논리주의적 시도를 무용지물로 만들기 위해서가 아니었다. 러셀 스스로가 애초에 논리주의의 일원이었다.

프레게도 그렇고 러셀도 마찬가지로 이러한 역설을 피하기 위해 집합이라는 개념을 다시 새롭게 정립한 뒤(계형 이론), 이것을 통해 다시 자연수 체계(페아노 공리 체계)의 공리들을 이끌어낼 수 있다고 여전히 믿었다. 실제로 러셀이 스스로 제시한 계형 이론과  ZFC 공리계는 프레게의 시스템을 전혀 손상하지 않았으며 수 체계에 대한 확고한 기초로 보였다.... (괴델이 등장하기 전까지는...)

 

 

 1-2. 힐베르트와 형식주의의 등장

 결국 수학사에서 비유클리드 기하학의 등장은 공리에 대한 의문을 낳았고, 러셀의 역설은 논리적 추론에 대한 의문을 낳았다. 이 두 가지는 수학의 기초이자 본질이기 때문에 최고의 수학자, 다비드 힐베르트에게 이 문제는 피할 수 없는 문제였다.

현대수학의 아버지, 다비트 힐베르트

힐베르트는 이 문제를 다음과 같이 해결하려고 시도했다. 힐베르트는 논리적 패러독스가 등장하는 이유를 그 패러독스가 지닌 의미론적 내용에 의해 생겨난다고 믿었다. 즉, 논리주의는 인간의 생각을 기초로 성립되어 있는데, 이는 인간의 생각이 근본적으로 품고 있는 한계에 의해 악영향을 받을 수 밖에 없다는 주장이었다.

논리주의에서 러셀의 모순이 발견된 것도 인간의 논리적 이성에는 한계가 있기 때문이다. 논리학이 타당하다는 믿음도 인간의 일방적인 믿음에 불과하지 않은가. 아무리 논리주의자들이 논리학을 정밀하게 다듬는다고 해도 모순이 없다고 확신할 수 없다.

따라서 힐베르트는 새로운 수학 방법론으로서 형식주의를 내세웠다. 형식주의는 논리주의와 완전히 대비되는 사조라기보단, 논리주의적 시도를 모두 포괄하는, 보다 더 메타적인 시도다. 논리학과 같이 인간적 사고의 내용과 의미에 기반을 두지 말고, 순수하게 수학 자체를 어떤 기계적 시스템으로 보자는 것이다.

지금껏 우리가 해 온 수학이란 무엇인가? 직관적으로 타당한 공리를 바탕으로 논리적 추론을 통해 참인 명제(정리)를 생각해내는 행위다. 그러나 공리에 대한 직관적 믿음은 비유클리드 기하학의 등장으로 산산조각나고, 논리적 추론 과정 또한 그 실체가 불명확하다는 것이 드러났다. 

그러니까 직관이나 논리와 같은 인간적인 요소를 배제해보자!. 인간적인 것에서 벗어난 수학의 실체는 그저 형식에 불과하다는 것이 금방 드러난다. 어떤 기호열을 어떤 규칙에 의해 다른 것으로 바꾸어나가는 변환 작업의 연속이다.

와닿진 않겠지만 수학하는 행위 자체를 최대한 일반화해서 표현하면 정말로 수학이란 하나의 게임에 불과하다. 수학적 명제란 잘 정의된 유한한 길이의 기호열로 볼 수 있다. (실제로 기호논리학은 이런 작업을 한다.) "모든", "어떤", "~이면 ~이다"와 같이 일상 언어가 기호로 변환된 경우도 있다. 그리고 이것을 다른 기호열(명제)로 변환하는 것이 '규칙'이다.

예를 들어, "A가 참이고 B가 참이면 A and B도 참이다"라는 문장을 "A, B -> A ㅅ B" 라는 기호열로 치환하는 것이다.

 

힐베르트의 형식주의에서는 특정한 유한한 수의 기호열이 주어지는데 이것이 공리다. 그리고 그 기호열을 다른 기호열로 바꾸는 일련의 유한한 수의 변형규칙이 주어진다. 주어진 기호열(공리)를 변형규칙을 통해 새로운 기호열을 만든다면 이것이 정리다. 이러한 시스템을 형식체계라고 부른다. 만약 어떤 기호열이 주어지고, 이것이 공리로부터 변형규칙을 유한 번 사용해 해당 기호열을 얻을 수 있다면 그것이 증명이다.

잘 보면 힐베르트가 말한 형식주의는 수학적 행위의 일반화라 할 수 있다. 프레게와 러셀이 시도한 논리주의 사조는 형식주의의 한 특수한 사례가 된다.

이러한 형식체계의 예시는 일상에서 쉽게 찾아볼 수 있는데 사실 게임(퍼즐 장르)이 바로 형식체계의 일종이다. 바둑도, 체스도 다 마찬가지다. 모두 일련의 규칙이 주어지고, 체스판 위에 말들이 놓여 있는 상태는 하나의 기호열로 생각할 수 있다.

콘웨이의 life game

콘웨이의 life game도 형식체계의 일종이다. 

2차원 배열에 초기 입력값 상태가 주어진다. 값의 존재와 위치, 그리고 보드판은 2차원 배열에 나열할 수 있으므로 하나의 기호열로 생각할 수 있다. 실제로 메모리 상에서 2차원 배열은 일렬로 나열된 array에 불과하다. 각각의 array의 값은 흑(1), 백(0)으로 표현할 수 있다. 따라서 기호열은 000110100010100.... 이런 형태로 충분히 변환 가능하다.

콘웨이의 life game은 놀라울 정도로 간단한 규칙에 의존한다. 위 4가지 규칙이 전부다. 콘웨이의 life game은 형식주의 관점에서 다음과 같이 생각할 수 있다.

기호(0과 1)와 그 배치가 잘 정의된 구조(배열)가 있으며, 최초로 참이라고 받아들일 수 있는 기호열이 주어진다. 이것이 공리다. 매 턴마다 적용되는 4가지 규칙은 변환규칙이다. 변환규칙을 통해 매 턴마다 색다른 패턴이 주어진다. 이것이 정리다. 꽤 많은 시간이 지나가고 나면 보드판 위에는 색다른 패턴이 존재할 것이다. 이 정리는 유한 번의 변환작업을 거친 결과이므로 그 반대 방향을 역추적할 수 있다. 즉, 증명될 수 있다.

센스가 좋다면 이러한 관점이 사실상 소프트웨어를 코딩하는 것과 똑같은 작업이라는 것을 금방 눈치챌 것이다. (이 즈음부터는 슬슬 컴퓨터라는 기계의 본질에 대한 단서가 잡히고 있다...!)

 

힐베르트의 형식주의는 수학적 행위에서 의미론적인 부분들(산술, 기하학, 해석학, ...)을 완전히 제거하고 남은 시스템이다. 따라서 형식체계 자체는 도저히 그 정체를 알 수 없는 기호열의 무의미한 나열과 변환으로 보일 지도 모른다. 형식주의에게 수학이란, 특정한 하나의 형식체계에 인간이 맥락과 의미를 부여하고 해석한 것에 불과하다.

그런데 이런 의문이 든다. 무의미한 기호의 나열에 불과하다면 왜 굳이 이런 식으로 수학을 생각해야 하는 것일까? 힐베르트의 궁극적 목표는 수학에서 의미론적인 것들을 배제함으로써 수학적으로 온전한 형식체계를 확보하는 것이었다.

즉, "수학"이라고 부를 수 있는 게임을 찾자는 것이다. 그리고 그 형식을 바탕으로 수학적 개념들을 인간 세계의 맥락에 따라 적당히 "해석"하는 것이 수학의 이상적인 모습이라고 생각했다.

이렇게 수학적 행위 자체를 러프하게(대략적으로) 해석하면 기호열 변환 게임이 된다. 이 세상에는 수많은 기호열 변환 게임이 있을 것이다. 수학은 그 중 하나다. 힐베르트는 수많은 기호열 변환 세계 중, 수학적으로 해석하기 타당한 형식체계를 찾는 것이었고, 이를 힐베르트 프로젝트라 부른다.

 

 

2. 힐베르트 프로젝트의 원칙

이제 관건은 무엇이 과연 수학적으로 해석하기 좋은 기호 형식체계인가 하는 문제다. 이에 대해 힐베르트는 아래와 같은 원칙을 내세웠는데, 상식적으로 충분히 받아들일 수 있는 원칙들이다.

1. 완전성 : 모든 참인 진술은 증명 가능하다. (즉, "모든" 참인 명제를 형식체계가 만들어낼 수 있다)
2. 무모순 : 형식체계로부터 만들어진 명제들은 서로 모순이 없어야 한다.
3. 증명은 유한하게 기술 가능해야 한다. (결정 문제)

1) 완전하지 않다면, 즉 모든 참인 명제를 만들어낼 수 없다는 말은 그 형식 체계 내에서 참인데도 불구하고 증명하지 못하는 무언가가 있다는 것이고, 이것은 이상적인 수학이 될 수 없을 것이다. 어떤 명제가 증명 불가능하다는 것은 증명을 업으로 삼는 수학자들에겐 청천벽력같은 소리다.

2) 그리고 만약 증명 가능한 정리들이 서로 모순이라면, 즉 똑같은 진술인데도 어떤 증명 과정에서는 참으로 판별나고 어떤 증명에선 거짓이라면 그것 또한 올바른 수학이라 할 수 없다. 모순이야말로 가장 받아들일 수 없는 성질일 것이다.

3) 마지막으로 유한한 증명 가능성은 만약 증명이 무한하다면, 즉 변환규칙이 무한하게 적용되어야 한다거나 무한한 공리가 사용되거나 한다면 그것은 설명 불가능하므로 애초에 이론이라할 수 없을 것이다. (이것은 나중에 멈춤 문제로 이어진다)

 

힐베르트는 수학의 기초를 확립하는 것이 목적이었으므로, 논리주의가 맞닥뜨린 최초의 문제, 바로 산술 체계(자연수 체계)의 기초가 될 수 있는 형식체계를 찾는 것이 궁극의 과제였다.

힐베르트는 이것이 가능하다고 믿었고, 볼로냐 선언에서 수학자들을 모아 이러한 형식 체계를 찾자고 선언한다. 이것이 힐베르트 프로그램이 시작된 역사다.