괴델, 에셔, 바흐
과학사상8호(1994년-봄) : Douglas R. Hofstadter 지음, BasicBooks, 1979, 민찬홍 (한남대 교수 · 철학), 범양사 출판부, Page 24~51
Ⅰ.《괴델, 에셔, 바흐 Gödel, Escher, Bach : Eternal Golden Braid》는 1979 년 미국에서 간행되었고 그 다음 해에 비소설부문의 퓰리처상을 수상하는 호프스태터 (D. Hofstadter, 1945 ~) 의 역저다. 이 책에서 저자가 설명하고 설득하려 하는 아이디어는 매우 많다. 무려 750 쪽이나 되는 방대한 책이나 많은 얘기를 담고 있다는 건 당연한 일이겠다. 그러나 이책의 주된 줄거리는 역시 수리논리학의 회귀이론 (recursion theory) 또는 회귀함수론 (recursive function theory) 이다. 이 책에서 우리는 '형식체계 (formal system)' 의 기본개념들로부터 시작해서 20 세기 수리논리학의 꽃이라 할 '괴델 정리 (Gödel Theorem)' 에 이르기까지 회귀이론의 줄거리에 대햐여 정확하고도 친절한, 게다가 흥미만점의 안내자를 만날 수 있다.
물론 현대 수리논리학의 중요한 성과를 설명하고 선전하는 것이 호프스태터가 전하려는 메시지의 전부는 아니다. 원래 컴퓨터 과학자인 저자는 괴델 정리에 도달하는 중간 길목들에서 의미와 해석, 컴퓨터의 상-하위 언어들, 정신과 사고 등에 대한 자신의 견해를 절묘하게 끼워넣고 있으며 마지막 부분의 두 장에서는 독자들에게 인공지능의 기본적 아이디어와 간단한 역사, 그리고 앞으로의 전망을 그려주고 있다.
하지만 인공지능학은 지난 10 년간 엄청난 변화를 겪었다. 그렇다면 인공지능에 대해서 말하는 책이 15 년 전에 쓰여진 거라면 혹시 너무 낡은게 아닌가? 아닌게 아니라 이책에서 '신경망' 이니 '병렬분산처리 (Paraller Distributed Proccessing)' 니 또는 '퍼지이론' 이니 하는 최근 인공지능학의 개념들을 찾아볼 수는 없다. 이책에서 다루는 것은 호질랜드 (J. Haugeland) 가 'GOFAI (Good Old-Fashioned AI)'1) 라고 불렀던 인공지능, 즉 정보를 직렬로 처리하는 디지털 컴퓨터를 모델로 한 인공지능이요, 컴퓨터나 인간의 두뇌나 본질적으로 기호를 조작하고 처리 (symbol manipulation) 하는 기계라는 점에서 일치한다고 생각하는 고전적인 (?) 개념의 인공지능이다. 그렇다고 해서 호프스태터가 설명하는 인공지능이 역사적 관심거리에 불과한 흘러간 옛 얘기라고 할 수는 없다. 인공지능학에 패러다임이란게 있다면 아직은 GOFAI가 그 자리를 고수하고 있는 것이다.
Ⅱ. 체코 태생의 수학자요, 논리학자였던 괴델 (K. Gödel, 1906 ~ 1978) 은 거의 '논리학의 아인슈타인' 이라고 불릴 만한 사람이다. 괴델은 1931 넌, 그러니까 25 세에 <수학 원리 (Principia mathematica) 및 그 연관체계에 있어서 형식적으로 결정불가능한 명제에 과하여> 라는, 내용도 몹시 어렵고 제목조차 접근을 허락치 않는 논문을 발표하여 거의 100 년간에 걸친 수학자들의 노력, 즉 수학의 전 영역을 포괄할 수 있는 공리체계를 확립하려는 노력에 종지부를 찍었다.
바흐는 대위법 (counterpoint) 을 완성한 고전시대 음악의 거장이며 에셔는 금세기에 활동한 화가다. 대위법이란 독립된 두 멜로디가 함께 또는 교차적으로 섞여서 연주되는 음악형식이다. 주 멜로디에 대한 반주 자체가 또 하나의 멜로디를 이루는 것이다. 17 세기까지 화성학은 자연과학의 한 분야로 간주되었을 정도로 화성학과 대위법 등 음악의 이론적 부분들은 매우 수학적인 구조를 갖고 있다. 음반을 판매하는 영업사원들은 "태아 때부터 바흐의 음악을 들려주면 아이가 전제가 된다" 느니 하는 별로 믿기지 않는 얘기를 주워섬기면서 천재 아이를 바흐는 부모의 황당한 기대를 부추기는가 하면, 한편으로 수리과학과 음악을 (바둑이나 체스와 함께) 나이 어린 천재가 등장할 수 있는 분야로 꼽으면서 음악과 수학의 관련을 거론하는 사람들도 가끔 있기는 하다. 그렇다 하더라도 괴델 정리와 바흐의 음악이 공유하는 논리적 구조를 찾겠다는 저자의 생각은 참으로 비약적인 발상이라 아니할 수 없다. 나는 호프스태터의 바흐에 대한 감탄을 공감할 만큼의 음악적 식견도 없는데다가 바흐 음악에 대한 설명을 썩 잘 이해할 수도 없었다. 게다가 바흐의 작품에 나타나는 회귀구조 (recursive structure) 가 과연 논리학의 회귀함수와 정말로 같은지에 대해서도 별로 긍정할 수가 없다. 그렇지만 그것으로 인해 논리학의 중요 개념에 대한 저자의 설명을 따라가는 데 방해받을 일은 없다. 그리고 혹시 음악과 수학 모두에 깊은 관심을 가진 독자라면 밤잠을 설치면서 읽게 될런지도 모르겠다.
한편 20 세기에 활약한, 그러나 별로 널리 알려지지 않은 화가인 에셔는 영원히 꼭대기에 올라설 수 없는 계단이라든지 감상자가 그림의 일부가 되고 있는 그림, 또 두 손이 서로 상대방을 그리고 있는 모습 등등 매우 자기지시적 (self-referring) 인 그림들을 그리고 있다. 그의 그림 중에는 어떤 형태 (예컨대 새들의 모양) 를 그리되 그 배경도 또한 같은 형태를 이루는 기묘한 작품들도 여럿 있는데, 이런 작품들은 '형태 (figure) 와 배경 (ground)' 의 구별에 대한 도전이라 할 만한 것으로 배경이 동시에 형태가 된다는 점에서 '회귀적' 이라는 개념의 정의에 잘 들어맞는다. 호프스태터는 에셔의 작품들을 화보 (비록 흑백이긴 하지만) 와 함께 설명하고 있다. 인상파 이후의 현대 회화에 대해서 완벽한 까막눈인 필자조차도 에셔의 그림들을 감상하는 데 아무런 문제가 없었다.
잊기 전에 꼭 알려드려야 할 것은 이 책의 각 장 사이에 아킬레스와 거북이의 긴 대화가 끼여 있다는 점이다. 바로 이 점 때문에 호프스태터는 " 루이스 캐럴의 정신에 입각해서 쓰여진…… " 이라는 구절을 부제에 넣은 것이라고 보여지는데 이 대화가 참 재미있다. 다 아시겠지만 캐럴 (L. Carroll) 은 19 세기의 논리학자인데 《이상한 나라의 앨리스》의 저자로 널리 알려진 사람이다. 캐럴은 운동을 부정했던 고대 그리스의 철학자 '제논 (Zenon) 의 역설' 의 그 아킬레스와 거북이를 등장시켜서 대화집을 냈다고 하는데, 호프스태터는 다시 캐럴을 흉내내어 이 책에서 다루고 있는 여러 가지 문젯거리들에 대하여 아킬레스와 거북이가 나누는 대화를 각장 사이에 엮어 넣고 있다. 이 막간의 대화들은 그냥 양념이 아니다. 대부분 다음 장에서 설명할 주제를 놓고 벌이는 토론으로 되어 있으며 때로는 이 대화를 읽지 않고는 다음 장의 설명을 따라가기 어려운 경우도 있다. 사실 이 책이 이렇게 두꺼워진 것은 대화들 탓이긴 하지만 이 대화들은 하나같이 호프스태터의 재기와 기지가 두드러지는 잘 짜여진 것들이다 (이 대화 중 몇 개는 실제로 캐럴의 작품이라고 그는 밝히고 있다).
Ⅲ. 어쨋든 앞서 말했듯이 이 책의 주된 주제는 괴델 정리라고 할 수 있으므로 이 책이 과연 어떤 책인지 맛보기 삼아서 논리학의 얘기를 해보기로 하자. 괴델 정리와 바흐의 작품, 그리고 에셔의 그림에서 공통적으로 찾을 수 있는 요소로 저자가 꼽고 있는 것은 대체로 두 가지로 말할 수 있다. 첫째는 자기지시 (self-reference) 요, 둘째는 회귀 (recursion) 인데, 물론 이 두 가지가 무관한 것이 아니다. 이 중에서 자기지시는 알려진 지 꽤 오래된 것이어서 그 대표적인 예가 성경에도 기록되어 있다. 그것이 바로 '거짓말쟁이 역설 (liar paradox) '이라는 것이다. 예를 들어서 다음 문장을 한번 생각해보자.
(L) L은 거짓이다.
만일 이 문장이 참이라면 이 문장은 거짓일 것이다. 또 만일 이 문장이 거짓이라면 이 문장은 참이 된다. 그러니 역설이 된다. 도대체 이게 왜 문제가 되나? 또 이런 일이 왜 발생하는가? 이것은 그리 답하기 쉬운 문제가 아니다. 대충 말한다면, 많은 사람들은 이런 역설은 우리의 언어가 너무 풍부해서 말 자체에 대해서 말하는 장치까지도 가졌기 때문에 발생한다고 생각한다. "서울은 큰 도시다" 에서 '서울' 은 서울이라는 도시를 가리킨다. 그러나 "서울은 두 글자다" 에서 '서울' 은 '서울' 이라는 말 자체를 가리킨다. 우리는 이러한 혼동을 피하기 위해서 어떤 말이 그 말 자체를 가리킬 때 앞뒤에 작은 따옴표를 한다. 그러니까 정확하게 쓰면 " '서울' 은 두 글자다" 라고 해야 옳다. 도시를 가리키는 말이 있고, 또 그 말을 가리키는 말이 있으니 이것을 분명히 구별해야 한다. 타르스키 (A. Tarski) 라는 폴랜드의 논리학자는 전자를 대상언어 (object language), 후자를 메타언어 (metalanguage) 라고 구별하여 거짓말쟁이 역설을 피하는 체계적인 방식을 세우려고 했다. 그리고 놀랍게도 괴델과 비슷한 결론에 도달하고 있다.
거짓말쟁이 역설이 문제가 되는 것은 우리의 이성이 모순을 용납할 수 없기 때문이다. 우리 사회가 모순투성이라느니 모순까지도 포용할 수 있어야 하지 않느냐느니 하는 말들을 가끔 들을 수 있는데, 오해가 있을까봐 사족을 붙이자면, 여기서 용납할 수 없는 모순이란 것은 그런 게 아니다. 가진 자들과 못가진 자들간의 갈등과 대립도 모순이라면 모순이고, 또 아내로서 깨끗하고 아름답게 꾸미고 지내야 하면서 동시에 엄마로서 집안의 온갖 허드렛일을 도맡아야 하는 주부도 모순된 기대역할을 안고 살아야 한다고 말할 수 있다. 그러나 논리학에서 말하는 모순이란 'p이면서 동시에 p가 아니다' 처럼 어떠한 경우에도 참이 될 수 없는 문장이 범하는 잘못이요, '결혼한 총각' 처럼 수퍼맨이나 하나님조차도 만들어낼 수 없는 대상을 가리키는 개념이 범하는 잘못이다. 만일 어떤 생각이 모순을 담고 있다면 그것은 어떤 세계에서도 참일 수가 없다. 그러니 진리의 체계를 세우려는 마당에 모순의 발생은 큰 문제가 아닐 수 없다.
괴델은 산수를 정식화할 수 있는 정도 이상의 풍부한 언어로 거짓말쟁이 역설을 일으킨 위의 예문과 같은 구조를 가진 문장을 만드는 방법을 고안해냈다 (호프스태터의 책에 이 방법이 자세히 설명되어 있다). 괴델의 문장은
(G) G는 증명될 수 없다.
라는 진리인 문장이다 (만일 G가 거짓이라면 어떻게 될까? 한번 생각해 보자). 이 문장이 참이므로 만일 어떤 체계가 G를 증명할 만큼 강하다면, 즉 G를 정리로 가질 정도로 강하다면 그 체계는 모순에 빠지게 된다. 거꾸로 만일 어떤 체계가 정합적이라면, 즉 모순을 함축하지 않는다면 그 체계에서 G는 증명될 수 없다. 그런데 G는 참인 문장이므로 그 체계는 참인 문장을 증명하지 못하는 셈이다. 즉 모순 없는 체계라면 그것은 완전할 수 없다. 참을성 있게 읽어나가는 독자라면 호프스태터가 괴델 정리의 전모를 충실하게 그리고 알아들을 수 있게 설명하고 있음을 발견하게 될 것이다. 물론 여기까지 도달하려면 이 책을 거의 다 읽어야 한다.
이제 회귀라는 개념에 대해서 말할 차례가 되었다. 논리학에서 회귀라는 말은 꽤 낯설게 들릴지 모르지만 사실 간단한 회귀함수는 고등학교 때 수학시간에 배운 것이다. 대부분의 사람들은 A1 = 1, An+1 = 2An + n (n □ 0) 라는 식으로 주어지는 수열의 표기법을 본 기억이 있을 것이다. 이것에 점화식이라는 이름이 붙어 있지 않았던가? 점화식이 바로 간단한 회귀함수이다. 당시에 수학 선생님들이 이걸 가지고 골치 아픈 문제들을 내곤 했다. 실제로 위의 식대로 자연수를 찾아서 차례로 써나가는 건 무지하게 쉽다. 1, 3, 8, 19, 42, 89, …… 뭐 이렇게 나가는 수열 아닌가? 이 수열의 항이 되는 자연수들의 계열을 S라고 하자. 그러면 S는 회귀적으로 계산가능한 집합 (recursively enumerable set) 이 된다 (여기에 대해서도 제대로 된 설명을 보려면 책을 직접 읽으시라). 임의의 자연수가 주어졌을 때 그 수가 S에 속하는지 안 속하는지 알 수가 있을까? 물론 알 수 있다. 위의 수열은 작은 수부터 시작해서 차례로 커진다. 그러니까 위의 수열을 계속 이어가서 문제의 수가 얻어지는지 아니면 그냥 넘어가는지 알아볼 수 있다. 문제의 수가 매우 큰 수라면 이건 매우 지겨운 일이겠다. 그러나 어쨋든 어떤 수가 S에 속하는지 아닌지는 분명하게 결정된다. 이러한 문제가 바로 결정과정 (decision procedure) 을 갖는 문제다.
그러면 소수 (prime number : 1 과 자기자신 이외의 약수를 갖지 않는 수) 의 계열은 어떨까? 주어진 수가 소수인가 아닌가 하는 문제는 결정과정을 갖는다. 그 수를 2 로 나누어보고, 3 으로 나누어보고, 4 로, …… 이렇게 그 수에 이르기까지 차례로 해보면 될 테니까 말이다. 그런데 모든 소수를 빠뜨리지 않고 찾아내는 점화식 (회귀함수) 을 찾을 수 있을까? 이건 좀 만만치 않을 것 같다. 그리고 이것이 마로 호프스태터가 얘깃거리로 삼은 문제가. 이 문제에 대한 답이 궁금하다면 이 책의 3 장까지만 읽으면 된다.
실제로 논리학과 수학에서 회귀집합의 개념은 논리적인 추리 또는 수학적인 연산들을 컴퓨터화하는 데 결정적으로 중요한 역할을 한다. 예를들어 내가 별달리 할 일이 없어서 심심풀이로 종이에 a, b, c 라는 세 글자로만 이루어진 나열을 하나 골라서
abccac
라고 쓰고서 제일 왼쪽에 a가 있는 것을 보고 이 나열의 오른편 끝에 bab라는 나열을 덧붙이고 왼편에서 세 글자를 지웠다고 하자. 그래서 나는
cacbab
라는 나열을 얻는다. 이 나열은 b로 시작하는 것을 보고 이 때에는 오른편에 cab를 붙이고 왼편에 세 글자를 지워서
babcab
라는 나열을 얻는다. 이제 이 나열은 b로 시작하는 것을 보고 이 때에는 오른편에 abba를 더하고 왼편에 세 글자를 지워서
cababba
를 얻는다. 얻어진 나열이 a로 시작할 때에는 언제나 왼편의 세 글자를 지우면서 오른편 끝에 bab를 붙이고, b로 시작할 때에는 언제나 왼편의 세 글자를 지우면서 오른편 끝에 abba를 붙이고, c로 시작할 때에는 언제나 왼편에 세 글자를 지우면서 cab를 붙이고, 이렇게 이 일을 계속한다면 나는 다음과 같은 나열들을 차례로 얻게 될 것이다.
abbacab
acabbab
bbabbab
bbababba
babbaabba
ㆍ
ㆍ
ㆍ
내가 처음에 쓴 나열부터 계속하여 얻어진 나열들의 집합은 앞서 말한 회귀적으로 계산가능한 집합을 이룬다. 그런데 이렇게 다음 나열을 얻는 일을 계속한다면 어떻게 될까? (1) 새로 얻는 나열이 이전에 얻은 나열과 똑같아져서 순환하는 나열의 고리와 만나거나, 또는 (2) 결국에는 나열이 점점 짧아져서 없어지거나, 또는 (3) 무한정 새로운 나열들을 얻으면서 계속되거나, 이 셋 중의 한 가지 경우에 속하게 될 것이다.
이 게임(?)은 포스트 (E. Post) 의 '덧붙이기 체계 (Tag system)'2) 라고 알려진 것인데 이 예만 갖고도 우리는 '기계적 과정' 에 대해서 중요한 개념들을 다 얻어낼 수 있다. 유한 개의 기호들의 집합 { a1 …… am} (우리의 예에서는 { a, b, c}) ; 유한 개의 순서쌍의 집합 { (a1, A1) , …… (am, Am) } (우리의 예에서는 { (a, bab), (b, abba), (c, cab)}) ; 하나의 정수 n (우리의 예에서는 n = 3) ; 그리고 처음에 주어지는 하나의 나열 A0 (우리의 예에서는 abccac) 가 주어지면 하나의 덧붙이기 체계가 결정된다. 이 체계에서 나열을 얻어내는 규칙은 다음과 같이 주어진다.
(규칙0) A0 를 집합 W 로 잡으라. (규칙1) 로 가라.
(규칙1) W 를 '목록' 에 저장하라. 이제 W 의 제일 왼편 기호가 a1이면 W 의 오른편 끝에 A1 을 덧붙이면서 왼편의 세 기호를 지우라. 이렇게 해서 얻어진 결과를 W 로 삼으라.
(규칙2) 만일 W 가 공집합이면, 즉 모든 것이 다 지워지면, (규칙3) 으로 가라. 그렇지 않으면 W 가 '목록' 의 어떤 항과 같은지 검사하라. 만일 같은 항이 발견되면 (규칙3) 으로 가라. 같은 항이 발견되지 않으면 (규칙1) 로 가라.
(규칙3) 멈추라.
(규칙3) 이 적용되면 그 체계는 멈추게 된다. 예를 들어서 {a, b, c}, {(a, bab), (b, abba), (c, ca)}, n = 3, A0 = cabcba 로 주어지는 체계는 같은 나열을 얻어서 멈추게 된다. 또 {a, b, c}, {(a, cac), (b. bab), (c, ca)} n = 3, A0 = cabcba 로 주어지는 체계는 모든 기호가 지워져서 멈추게 된다. 이건 길지 않으니까 약 5 분이면 각자 확인해볼 수 있다.
하나의 덧붙이기 체계가 주어지면 어른이든 아이든 기계든 그 체계가 멈추는지 아닌지를 알아보려고 몇 시간이고 몇 주간이고 덧붙이기 게임을 할 수가 있다. 그러므로 덧붙이기 체계는 기계적으로 계산될 수 있는 체계다. 규칙의 적용에 있어서 애매한 구석도 없고 어떤 창조적인 직관이 개입할 여지도 없는 것이다. 이것이 바로 '기계적 과정' 의 핵심이 된다. '효율적 과정 (effective procedure)' 이라고 불리기도 하는 기계적 과정은 유한 개의 기호들을 읽고, 쓰고, 저장하고, 지우고, 두 기호가 서로 같은지 검사하는 일만으로 수행될 수 있는 과정이다 (기계적 계산과정이 과연 무엇인지 정확하게 정식화하기는 어렵다. 이에 대해서는 여러 논리학자 나름대로 규정지었는데 이들의 규정이 실제로 동등하다는 것이 밝혀져 있다. 사람들은 이 점을 들어서 '기계적 과정' 을 정확한 정의 없이도 받아들일 만한 개념이라고 여긴다). 그런데 주어진 덧붙이기 체계가 멈추는가 아닌가를 결정해주는 결정과정은 있을까? 컴퓨터에게 어떤 덧붙이기 체계를 주고서 그것이 멈추는지 알아보도록 해보자 (사람한테 시키면 누가 이 지루한 일을 하려고 하겠는가?). 만일 이 체계가 멈춘다면 컴퓨터는 멈춘다고 알아낼 것이다. 그러나 이 체계가 멈추지 않는다면 어떤가? 컴퓨터는 계속해서 (고장날 때까지) 다음 나열을 얻어갈 것이다. 이 경우에 우리는 이 체계가 조금 더 있다가 멈출지 계속 해나갈지 알 수가 없다. 그러므로 '어떤 덧붙이기 체계가 멈추는가' 하는 문제는 효율적인 결정과정을 갖지 않는다. 포스트가 제시한 덧붙이기 체계에 이런 것이 있다 :
{ 0, 1 }, { (0, 00 ), (1, 1101 ) }, n = 3, A0 = 100100100100100100100.
이 체계가 멈출까 아니면 무한히 계속될까? 궁금하더라도 해보려고 하지 마시길 ……. 이 체계에 대한 조사가 사람들은 물론이고 컴퓨터까지 동원되어서 이루어졌지만 아직도 이것이 멈추는지 무한정 계속되는지 알려지지 않고 있다 [수백 년간 안 풀리던 페르마의 마지막 정리 (Fermat's Last Theorem) 도 증명이 되어서 수학자들이 지금 검증중이라는데 이건 왜 안풀릴까?].
이와 비슷한 형식체계들로 호프스태터는 MIU-체계, pq-체계, TNT-체계 등을 소개하여 다루고 있는데, 이를 통하여 형식체계, 나열, 정리, 공리, 추리규칙, 결정과정 등 수리논리와 회귀이론의 기본 개념들을 알기 쉽게 설명하고 있을 뿐 아니라 가능할 때마다 바흐의 음악, 에셔의 미술 작품들에서 이러한 개념들에 대응하는 요소를 끄집어낸다. 어떤 부분은 비유에 불과한 것 같기도 하고 어떤 부분은 매우 정확한 것 같기도 한데 음악도 미술도, 게다가 논리학도 잘 모르는 필자에게는 이 점이 매우 어렵고 불분명하다. 이 점 여러분께서 읽으면서 판단해주시길 바란다.
주
1) Haugeland, J., Artificial Intelligence : The Very Idea (Cambridge, MA : The MIT Press / A Bradford Book, 1985).
2) Post, E., "Formal reductions of the general combinatorial decision problems," (1943) in Davis, M., The Undecidable (New York : Raven Press, 1965).