1931년, 당시 24세였던 '쿠르트 궤델(독일어: Kurt Gödel, 1906~1978)'은 '불완전성 정리(Incompleteness Theorems)'를 내밀어 수학계를 충격에 빠뜨렸다. 수학의 불완전함을 나타내는 '불완전성 정리'는 '수학적 증명이 불가능한 것은 없다'는 당대 분위기를 반전시켰다. 원자 폭탄을 개발한 주도한 이론 물리학자 '로버트 오펜하이머(Robert Oppenheimer, 1904~1967)'는 '불완전성 정리'에 대해 "인간의 이성 일반에서의 한계를 밝혀냈다."라고 평했다. '불완전성 정리'는 수학뿐만 아니라, 인간이 구축하는 어떤 시스템도 불완전하다고 제시한 것이다. '불완전성 정리'가 제시하는 '불완전(Incompleteness)'이란 무엇을 의미하는 것일까? 그리고 '불완전성 정리'는 세상에 어떤 영향을 미쳤을까?
0. 목차
- 한 번 증명된 정리는 영원히 뒤집히지 않는다.
- '제1 불완전성 정리'와 '제2 불완전성 정리'
- '불확정성 정리'의 이미지에 다가가기
- '괴델'은 공리계 전체를 수로 변환해 증명하였다.
- 힐베르트 프로그램
- 컴퓨터의 원형 '튜링 머신'
1. 한 번 증명된 정리는 영원히 뒤집히지 않는다.
수학과 논리학에서는 객관적으로 옳은지 아닌지 확인할 수 있는 글과 식을 가리켜 '명제(Proposition)'라고 한다. 예컨대 '7919은 소수이다'라는 글은 진위를 확인할 수 있기 때문에 명제이다. 참고로 7919는 소수이므로, 이 명제는 옳다. 옳음이 증명된 명제를 '정리(Theorems)'라고 한다. 예컨대 직각삼각형의 변의 길이에 관한 '피타고라스 정리(Pythagorean theorem)' 등의 정리가 있다. 세상에 존재하는 수많은 정리도 처음에는 진위가 밝혀지지 않은 명제였다. 하지만 그것을 수학자들이 하나씩 증명하여 '정리'가 되었다. 수학에서는 한 번 옳다고 증명된 정리는 영원히 뒤집히지 않는다. 그것은 논의의 전제가 되는 약속한 사항이 분명히 정해져 있고, 그 약속한 사항을 바탕으로 엄밀하게 증명이 이루어졌기 때문이다.
수학에서 가장 기본이 되는 약속 사항을 가리켜 '공리(Axiom)'라고 한다. 예컨대 '기하학(Geometry)'으로 말하면, '임의의 점에서 임의의 점까지 직선을 그을 수 있다'나 '중심과 반지름이 정해지면 원을 그릴 수 있다.'와 같은 것이 '공리'이다. 아주 당연하게 들리겠지만, 수학은 이런 기본이 되는 공리를 분명히 정함으로써, 누구나 똑같은 전제 조건의 바탕에서 논의할 수 있다. 기하학 등의 여러 이론 체계에서, 그 출발점이 되는 공리의 모임을 '공리계(Axiomatic System)'라고 한다. '공리계'는 법체계에서의 '육법(헌법, 민법, 상법, 민사 소송법, 형법, 형사 소송법의 6개)'에 해당한다고 할 수 있다. '육법'을 기본으로 여러 법률이 만들어지듯이, 수학의 공리계를 바탕으로 여러 정리가 증명되어 '기하학' 등 여러 이론 체계가 구축되는 것이다.
2. '제1 불완전성 정리'와 '제2 불완전성 정리'
'불완전성 정리'에는 '제1정리'와 '제2정리'가 있다. 이들이 의미하는 내용을 하나하나 풀어서 살펴보자.
- 제1 불완전성 정리: 자연수론을 포함하는 모순 없는 공리계에는 '결정 불가능한 명제'가 있다.
- 제2 불완전성 정리: 자연수론을 포함하는 모순 없는 공리계 내부에서는 그 무모순성을 증명할 수 없다.
'제1 불완전성 정리'에 등장하는 '자연수론'이란 '자연수(1, 2, 3···)'의 계산법이나 성질을 다루는 수학이다. 초등학교 수학에서 배우는 자연수의 덧셈이나 곱셈도 자연수론에 포함된다. '모순 없는 공리계'란 논의의 출발점이 되는 여러 공리 사이에 모순이 없다는 것이다. 공리 사이에 모순이 없는 것은 논의의 대전제이며 수학에서는 필요 불가결하다. 그리고 '결정 불가능한 명제'란 '그 공리계의 내부에서 참인데도 불구하고 증명 불가능한 명제' 다시 말해 '옳다고 하더라도 증명할 수 없는 명제'이다.
'불완전성 정리'의 '불완전'이란 공리계 내부에 이런 결정 불가능한 명제가 존재한다는 의미이다. '불완전성 정리'는 예컨대, 아무리 완전한 법률 체계를 만들어도 그 법으로는 붙잡을 수 없는 '빠져나갈 구멍'이 반드시 존재함을 증명한 것과 같다. 사회가 변하면 기존 법률로는 단속할 수 없는 새로운 범죄가 나온다. 그래서 우리는 새로운 법률을 만들어서 신종 범죄에 대응하려고 한다. 하지만 범죄자는 다시 법률에서 '빠져나갈 구멍'을 찾아내고, 새로운 법률로도 제재할 수 없는 범죄 행위를 되풀이한다. '불완전성 정리'는 수학에서 유사한 일이 생김을 증명한 것이다.
아무리 증명이 어려운 수학의 명제도 수학이 발전해 새로운 정리를 발견하면, 그 정리들을 사용해 언젠가 '진위를 결정할 수 있을 것(증명하거나 반증할 수 있을 것)'이라고 많은 수학자들은 믿어왔다. 그러나 '괴델'은 그러한 수학자들의 믿음을 완전히 박살 냈다. 아무리 수학이 발전해 새로운 공리와 정리를 추가해도 '증명도 반증도 할 수 없는 명제'가 존재함을 보여준 것이다.
'제2 불완전성 정리'를 알기 쉽게 말하면, '자기 자신에게 모순이 없음을 자신은 증명할 수 없다'는 의미이다. '제2 불완전성 정리'는 '공리계에 모순이 없는 명제'를 공리계 내부에서 증명할 수 없음을 보여준다. 즉 '공리계에 모순이 없다'는 것은 '결정 불가능한 명제'이다. 그런의미에서 제2정리는 제1정리의 구체적인 예시이다.
3. '불완전성 정리'의 이미지에 다가가기
'불완전성 정리(Incompleteness Theorems)'의 '증명 순서'와 '그 의미'를 이해하려면 고도의 수학과 논리학 지식이 필요하다. 그래서 여기에서는 어떤 특수한 섬을 무대로 하는 논리 퍼즐을 사용해 '쿠르트 궤델'의 사고를 모방하면서 '불완전성의 정리'의 이미지에 다가가보도록 하자.
3-1. '엘프'와 '오크'가 사는 섬
어떤 섬에 '엘프(Elf)'와 '오크(Orc)'의 두 종류의 주민이 살고 있으며, '엘프'는 진실만 말할 수 있고 '오크'는 거짓말만 할 수 있다. 단, 외모와 목소리는 같아 누가 '엘프'인지 '오크'인지 알 수 없어서, 어떤 주민이 '엘프'인지 '오크'인지는 발언 내용으로부터 판단해야 한다. 하지만 발언 내용만으로는 '엘프'인지 '오크'인지를 판단할 수 없는 경우도 있다.
- '나는 진실만 말한다.'라고 말한 경우: '나는 진실만 말한다.'라고 말하는 주민이 있다고 하자. 이 경우, '엘프'가 진실을 말했을 수도 있고, '오크'가 거짓을 말했을 수도 있다. 따라서 이 말을 하는 사람이 '엘프'인지 '오크'인지 알 방법이 있다.
- '나는 거짓만 말한다.'라고 말한 경우: '나는 거짓만 말한다.'라고 말하는 주민이 있다고 하자. 이 경우, '엘프'가 거짓을 말했을 수도 없고, '오크'도 진실을 말했을 수도 없다. 따라서 이 말을 하는 사람이 '엘프'인지 '오크'인지 알 방법이 없다.
'엘프는 진실만 말하고, 오크는 거짓만 말한다.'는 규칙을 따르는 한 '엘프'와 '오크'는 무슨 말이나 자유롭게 발언할 수 있다. 하지만 '나는 진실만 말한다.'나 '나는 거짓만 말한다.'처럼 절대로 발언할 수 없는 문장이 존재한다. 이 섬의 주민은 '나는 엘프다.'라고 말하거나 '나는 오크다.'라고 말할 수도 없다. 이렇게 발언할 수 없는 문장이 바로 공리계에서의 '결정 불가능한 명제'의 이미지이다.
3-2. '엘프'라고 증명되면 가입할 수 있는 클럽
실은 이 섬에는 '엘프 클럽(Elf Club)'과 '오크 클럽(Orc Club)'라는 한정된 주민이 가입할 수 있는 클럽이 있다. 명칭에서도 짐작할 수 있듯이 '엘프 클럽'에는 '엘프'만 가입할 수 있고 '오크 클럽'에는 '오크'만 가입할 수 있다. 클럽에는 가입 조건이 있는데, 그것은 이미 클럽에 가입된 회원이 '미가입 주민이 '엘프'와 '오크' 중 어느 한쪽이라고 증명하는 것이다. 예컨대 이미 '엘프 클럽'에 가입된 엘프에 의해 미가입 주민이 '엘프'임이 증명되면, 그 주민은 '엘프 클럽'에 가입할 수 있다.
이 섬에서는 논리학의 전형적인 추론인 '모두스 포넨스(modus ponens)'에 의해 증명이 이루어진다. '모두스 포넨스'는 '삼단 논법'의 일종으로 다음과 같은 것이다. '전제 1'이 '만약 A라면 B이다'이고, '전제 2'가 'A이다'이면, '고로 B이다'라는 '결론'을 낼 수 있다. 예를 들어 '전제1'이 어떤 수가 2의 배수일 때 그 수는 짝수이다'이고, '전제 2'가 '4는 2의 배수이다'이면, '4는 짝수이다'라는 '결론'을 낼 수 있다.
실제로 '4는 짝수이다'라고 발언하는 클럽 미가입 주민 X가 있다고 하자. 이 발언이 옳은지를 '모두스 포넨스(modus ponens)'에 의해 증명하려면 '전제 1'과 '전제 2'의 옳음이 증명되어 있어야 한다. 즉 '전제 1'과 '전제 2'를 이야기하는 것은 '엘프 클럽'의 회원이어야 한다. 다시 말해, '전제 1'과 '전제 2'를 이야기하는 '엘프 클럽' 2명이 X에게 가서 그 발언이 옳음을 증명할 수 있다. A의 발언이 옳음이 증명되면, A는 '엘프 클럽'에 가입할 수 있다.
3-3. 섬의 시스템은 모순이 없는데도 불완전
실은 '엘프 클럽 회원'은 섬의 모든 '엘프'를 '엘프 클럽'에 가입시키겠다는 야망을 가지고 있다. 그래서 '엘프 클럽'의 회원은 클럽에 가입되지 않은 주민에게 닥치는 대로 말을 걸어 '증명' 또는 '반증'하려고 한다. 주민의 발언 내용에 따라 그것을 증명하기 위해 필요한 '전제 1'과 '전제 2'를 이야기하는 '엘프 클럽 회원'이 달려들어 증명하는 것이다.
그런데 이때 주민 Y가 등장했다. Y는 '나는 엘프 클럽 회원이 아니다'라고 말했다. '엘프 클럽 회원'은 이 발언이 옳음을 증명해 클럽에 가입시킬 수 있을까? Y가 '엘프'라면 아무런 문제가 없다. 하지만 Y가 '오크'라면, 발언이 거짓말이므로 '엘프 클럽 회원이다'라고 말하는 것인데, 이렇게 되면 '오크'인 것과 모순이 생긴다. 즉, Y를 '엘프 클럽'에 가입시킬 수 없다. 모든 '엘프'를 '엘프 클럽'에 가입시키고자 하는 야망은 모두 물거품이 되었다.
'엘프'와 '오크'의 두 종류 주민으로 이루어진 이 섬은 '불완전성 정리'에 등장하는 '모순 없는 공리계'와 같다. 이 섬의 '공리'는 '엘프는 진실만 이야기하고, 오크는 거짓말만 한다'는 것이다. 그리고 발언 내용이 증명되면 '엘프 클럽'에 가입하고, 반증되면 '오크 클럽'에 들어간다. '엘프'인 동시에 '오크'일 수 없고, '엘프 클럽'과 '오크 클럽'에 동시에 가입할 수 없기 때문에, 섬의 시스템에는 모순이 없다. 그런데도 Y와 같은 주민이 존재하기 때문에, 섬의 모든 주민을 어느 한쪽에 가입시킬 수 없다. 즉 참인데도 증명할 수 없는 명제이기 때문에, 증명 또는 반증할 수 없다. 증명도 반증도 할 수 없는 '결정 불가능한 명제'가 존재한다는 것은 이 섬의 시스템이 불완전함을 의미한다. 이 섬에서 일어난 일이야말로 괴델이 불완전성 정리로 제시한 이미지이다.
4. '괴델'은 공리계 전체를 수로 변환해 증명하였다.
'엘프 클럽(Elf Club)'과 '오크 클럽(Orc Club)'의 이야기는 '쿠르트 궤델'의 '불완전성 정리'의 증명 방법과 비슷하다. 단 '쿠르트 궤델'이 이런 비유를 한 것은 아니다. 실제로는 수학의 공리계를 '괴델 수'라는 자연수로 변환해 코드화한 뒤, 소수의 성질과 논리학의 기술을 사용해 매우 교묘하게 증명하였다.
'괴델 수(Gödel Number)'는 수학과 논리학 기호에 특정 소수를 할당함으로써 표현된 특수한 수이다. 현대의 컴퓨터는 '숫자', '문자', '영상' 모두 0과 1의 나열로 코드화한 뒤 처리한다. '괴델로의 변환(괴델수화)'도 컴퓨터의 코드화와 비슷하다. 괴델은 괴델 수를 사용해 수치와 명제 등을 포함하는 자연수론의 공리계 전체를 자연수로 변환하고, 그 공리계 내부에 결정 불가능한 명제가 존재함을 증명했다. 참인데도 증명할 수 있는 명제를 '괴델 명제'라고 한다. 괴델은 자연수론의 공리계 내부에 '괴델 명제'가 존재함을 증명했다. 아무리 복잡한 수학의 공리계라도 자연수론의 공리계를 포함하기 때문에, 모든 진리를 증명하는 공리계를 수학의 세계에 구축하기란 불가능함을 밝힌 것이다.
수학계에는 오래전부터 알려져 있는데도 불구하고, 아직 증명할 수 없는 명제가 몇 가지 존재한다. 그 가운데 몇 가지는 현재 사용되는 자연수론의 공리계 내부에서는 '결정 불가능한 명제'일 가능성이 있다. 예컨대 '골트바흐의 추측(Goldbach's conjecture)' 등이 '결정 불가능한 명제'일 수 있다. 괴델은 자연수론의 공리계에 한계가 있음을 보여주었다. 즉, 자연수론의 공리계로는 커버할 수 없는 '결정 불가능한 명제'가 존재함을 증명한 것이다.
5. 힐베르트 프로그램
1920년대에 '현대 수학의 아버지'라고 불리는 독일의 수학자 '다비트 힐베르트(David Hilbert, 1862~1943)'가 중심이 되어 수학계에서는 '힐베르트 프로그램(Hilbert Program)'이 추진되었다. 이것은 당시 '집합론(Set Theory)'이라는 수학 분야에서 발견된 모순을 한 번에 해결하려는 계획이었다. 그리고 '힐베르트 프로그램'의 최대 목적은 수학의 공리계가 완전하며, 모순이 없음을 보여주는 것이었다.
'쿠르트 궤델'의 '불완전성 정리'는 이 계획이 진행되는 도중에 투하된 핵폭탄과 같았다. 1920년대 당시 거의 모든 수학자는 수학이 완전하다고 믿고 있었다. 즉, 아무리 어려운 명제라도 언젠가는 반드시 참인지 거짓인지를 증명할 수 있다고 믿고 있었던 것이다. 그러나 '궤델'은 그것이 근원적으로 불가능함을 증명하였다. 수학의 공리계가 모순이 없다는 것에 대해서도 '쿠르트 궤델'은 '제2 불완전성 정리'를 통해 그 공리계 내부에서는 증명할 수 없음을 보여주었다. '불완전성 정리'의 등장은 당시의 수학자들에게 악몽과도 같은 일이었다.
'불완전성 정리'를 발표하기 2년 전에 '괴델'은 자신의 박사 논문으로 '완전성 정리'를 발표했다. 이것은 '고전적인 논리학의 범위이면 공리계는 완전하다', 즉 '참이면 반드시 증명할 수 있음'을 보여준 것이다. 즉, '괴델'은 논리학은 완전하지만, 거기에 자연수론을 더하면 불완전해진다는 것을 명확히 보여 주었다. 당시 수학은 논리학에 포함된다는 '논리주의(Logism)'라는 사고가 있었다. 그러나 '괴델'은 '논리주의'가 성립하지 않음도 명확히 증명한 셈이다.
6. 컴퓨터의 원형 '튜링 머신'
6-1. 괴델-튜링 불완전성 정리
'괴델'이 1931년에 '불완전성 정리'를 발표하고 나서 5년 뒤, 1946년에 수학자 '앨런 튜링(Alan Turing, 1912~1954)'는 '계산 가능한 수와 결정 문제의 응용에 관하여'라는 제목의 논문을 발표했다. 그는 이 논문에서 현대 컴퓨터의 동작 메커니즘으로 이어질 아이디어인 '튜링 머신(Turing Machine)'을 발표했다. '튜링 머신'이란 칸으로 구획된 무한한 길이의 '테이프(Tape)'와 테이프 위의 칸에 기호를 읽고 쓰는 '헤드(Head)', 그리고 정보를 일시적으로 기억해두는 '기억 장치(Memory Unit)'로 구성된 가상의 기계이다.
'헤드(Head)'는 테이프 위를 1칸씩 좌우로 이동할 수 있다. '헤드'는 칸에 적힌 정보를 읽어 들인 뒤, '알고리즘(동작 규칙)'에 따라 칸의 정보를 바꿔 적거나 '기억 장치' 안의 정보를 변경하거나 좌우 어느 쪽의 칸으로 이동한다. 어떤 조건을 만족하면 '헤드'의 움직임은 멈춘다. '알고리즘(동작 규칙)'을 정해 두면, '튜링 머신'에 자동으로 복잡한 계산 등을 시킬 수 있다. 그리고 동작이 종료되면, 계산 결과를 출력해 준다. '튜링 머신'의 개념은 '자동으로 계산을 하는 기계', 즉 '컴퓨터(Computer)'의 원형이 되는 개념이다. '튜링 머신'은 정해진 알고리즘에 따라 자동으로 계산을 할 수 있다. 알고리즘을 복잡하게 하면, 그만큼 복잡한 고도의 계산을 할 수 있다. 이론적으로는 '계산'뿐만 아니라 인간과 똑같은 사고 회로를 가진 '생각하는 기계'도 만들 수 있다. 말하자면 '인공지능(AI)'이다.
실은 여기에도 '불완전성 정리'가 등장해 '한계(Limit)'를 정하게 된다. '튜링 머신'도 약속 사항을 쌓아 구축된 일종의 '공리계(Axiomatic System)'이다. 그래서 '튜링 머신'이 아무리 고도화되어도 수학적으로 '불완전'하다. 즉, '튜링 머신'은 만능이 될 수 없으며, '튜링 머신'이 절대로 풀 수 없는 문제가 존재한다. 이것은 '괴델'의 '불완전성 정리'를 확장한 '괴델-튜링 불완전성 정리'로 알려져 있다. '괴델-튜링 불완전성 정리'는 '모든 진리를 증명하는 튜링 머신은 존재하지 않는다는 것을 보여주었다.
6-2. 인간 기계론
'앨런 튜링(Alan Turing)'은 '기계도 생각할 수 없을까?'라는 주제를 수년 동안 생각했다. '앨런 튜링'은 '기계는 생각할 수 있다'고 믿었으며, '기계는 생각할 수 없다'는 9종류의 반대 의견에 대해 논문에서 하나하나 열심히 반론했다. '앨런 튜링'은 인간의 사고는 모두 알고리즘으로 환원될 수 있다'고 생각했으며, 이것은 '인간의 사고 과정은 컴퓨터 프로그램으로 기록할 수 있다'는 것이다. 즉 '앨런 튜링'은 인간도 '튜링 머신'의 일종에 지나지 않는다고 생각했다. 이런 사고방식을 '인간 기계론'이라 한다.
한편 '괴델'은 '인간의 정신은 어떤 유한 기계도 넘어선다'라고 생각해 '인간 기계론'에는 반대했다. '불완전성 정리'에 따라 '튜링 머신'에는 한계가 있다. 대략적으로 말하면, '괴델'은 그 한계의 존재를 알아차린 것은 인간 정신이 기계보다 낫기 때문이라고 생각했다. '앨런 튜링'은 무신론자였고, '쿠르트 궤델'은 신의 존재를 믿었다. 두 사람의 종교관 차이도 '인간 기계론'에 대한 사고방식이 영향을 미쳤을지도 모른다.