history of computability

 

 계산이론의 역사에 관해서는 Robert. I soare의 저술을 보는 것이 좋다. 매우 체계적으로 아이디어들이 역사적으로 어디서 튀어나왔는지 알 수 있다.

 

http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

www.people.cs.uchicago.edu

 

 

http://www.cs.umd.edu/~gasarch/BLOGPAPERS/soareturing.pdf

www.cs.umd.edu

 

 

 

 

이들의 역사를 보면 침울해진다. 학문의 초기단계라고 하더라도 계산이론의 기초를 이루는 모든 중요한 정리들이 20대 초반의 학생들에 의해 증명되었다.

 

 

 간략한 역사로 보자면, 계산이론의 역사는 수학의 엄밀성에 대한 요구에서부터 찾아볼 수 있다.

 

 시기로 보자면 이미 뉴턴시대에는 미적분학에 대한 엄밀한 정의가 없었고, 이것이 19세기가 되어서 큰 문제가 되었다. 말하자면 수학의 기초에 대한 엄밀한 정의가 주어져야 한다는 생각들이 많이 일어났고, 수학자들은 수학의 기초는 자연수에서부터 찾아야 한다고 결론을 지었다ㅡ이는 매우 자연스러운데, 초등학생 때부터 고등학생까지를 생각해보면 자연수부터 시작해서 실수로 건너갔다ㅡ. 즉, 수학에 대한 엄밀성을 따지는 것은 자연수체계를 엄밀하게 제시하는 것과 연관이 있었다. 이 작업들은 대개 19세기 후반부에 이루어졌다. 자연수에 대한 엄밀한 체계는 대표적으로 페아노가 제시한 공리계가 있다. 이 체계로부터 우리가 믿어온 모든 수학적 작업들이 엄밀하게 증명될 수 있었다. 이 때가 19세기 말이었다.

 

 비슷한 시기에 또 다른 수학의 부흥이 있었다. 칸토어라는 학자가 집합이라는 개념을 엄밀하지는 않지만, 개념적으로 정의하게 되었다. 그는 집합을 "어떤 조건을 만족하는 상상할 수 있는 대상들의 모음"과 비슷한 식으로 정의를 내렸다. 수학적으로 엄밀하게는 아니지만, 집합에 대한 개념 자체가 제시된 것만으로도 이는 엄청난 발전이었다. 칸토어는 이렇게 집합을 정의내리고 집합에 관한 일반적인 성질을 증명하기 시작했다.

 

 집합론과 관련해서 또 다른 흥미로운 부흥이 있었다. 흔히 알려진 러셀의 역설과 관련한 이야기다. 이를 알기 위해서는 프레게라는 인물을 알아야 한다. 프레게는 19세기 후반, 20세기 초반에 활동한 수학자로, 사실상 현대수학의 조상이라고 볼 수 있는 인물이다. 그는 아리스토텔레스부터 내려왔던 아주 기초적인 논리학(가령 삼단논법)을 엄밀히 제시하는 작업을 했다. 그는 and, or, not, for all, there is, if then등 수학에서 기초적으로 쓰이는 일상용어들을 기호로 제시했다. 그리고 그것들을 바탕으로 논리학을 기호화했다(이것이 일차논리의 기반이 되었고 기호논리학의 시초가 되었다). 프레게는 모든 수학을 위와 같은 기초적인 논리학적 용어로 환원하려고 했었다. 이는 논리주의로 불리는데, 프레게는 자신의 기호를 바탕으로 수학적 개념들을 논리적 개념으로 환원하는 작업을 했다. 그러나 이 작업은 실패로 끝났는데, 여기에 바로 러셀이 등장한다.

 

 러셀은 프레게의 작업들을 보고, 치명적인 오류를 발견하게 되는데, 그것은 바로 프레게가 암묵적으로 '모든 집합을 원소로 가지는 집합이 존재한다'를 가정하고 있었기 때문이었다. 러셀은 그런 집합이 없음을 증명하여 프레게에게 편지로 보냈고, 이로 인해 프레게의 논리주의는 종말을 맞게 되었다.

 

 흥미롭게도 페아노, 칸토어, 프레게, 러셀이 모두 겹치는 시기가 오게 된다. 러셀의 역설은 프레게의 논리주의를 종결내기도 하였지만, 그의 수학에 대한 공헌은 바로 '모든 집합을 원소로 가지는 집합'이 없다는 것이었다. 말하자면, 우리가 {}기호로 만드는 것들이 모두 집합이 되지는 않는 사실이다. 이는 바로 칸토어의 집합론(현대에 소박한 집합론이라고 부르는)에 대한 문제제기를 낳게 되었다. 이에 의해 집합의 개념을 축소해야하는 일이 벌어졌고, 집합론을 페아노 공리계와 같이 공리들로부터 따라나오는 대상들로 제한하는 일을 만들게 했다. 이 작업을 한 것이 제르멜로와 프렌켈이었고, 이를 ZF 혹은 ZFC 집합론이라고 한다.

 

 한가지 언급해야 할 것은, 프레게는 수학을 논리적 언어로 환원하기 위해서 자연수를 논리적 언어로 환원하려고 했었다는 점이다. 기존의 수학자들이 수체계에 대한 엄밀성을 요구한 것이 자연수에 대한 엄밀성을 요구하는 것이었기 때문에, 프레게 역시 비슷한 방식을 채택했었다. 앞에서 언급했듯이 이 작업은 실패로 돌아갔으나, 프레게가 했던 자연수를 논리적 언어로 환원하려는 방식은 ZF 집합론에서 집합으로 자연수를 정의하는 방식으로 채택되게 되었다.

 

 ZF 집합론은 자연수를 정의하는 것에 성공했고, 따라서 정수, 유리수, 실수, 복소수 체계를 집합으로 정의하는 것에 성공하였다. 이 작업을 바탕으로 현대 수학의 기반이 세워졌고, 현대 수학의 모든 언어는 이를 바탕으로 ZF 집합론을 바탕으로 세워지게 되었다.

 

 ZF 집합론이 마냥 완전한 것은 아니었는데, 이는 선택공리라는 특이한 공리 때문이었다. 수학에서 일반적으로 집합에서 원소를 뽑을 수 있다는 추론을 너무 당연하게 하는데, 이것이 어떻게 정당화될 수 있는가라는 문제가 당시 있었다. 제르멜로, 프랜켈은 이것을 해결할 수가 없었기 때문에 '원소를 뽑을 수 있다'는 것을 공리로 삼았다ㅡ유한한 집합에서 유한한 원소를 택하는 것은 직관적으로 분명하지만, 만약 집합의 크기가 무한할 때, 우리는 원소를 무한히 뽑을 수 있는가?라는 문제다ㅡ. 당시 수학에서는 이 선택공리가 과연 ZF 집합론에서 증명이 가능한가가 문제시되었다. 이것은 우리 주제가 아니기 때문에 넘어갈 것이지만, 언급만 하자면 괴델과 코헨에 의해 선택공리는 ZF 집합론으로부터 증명도 반증도 되지 않음(즉 독립적)이 증명되었다.

 

 

 ZF 집합론이 세워지고, 수학에는 흥미로운 사조가 등장했다. 힐버트가 제창한 입장인데, 수학에서 참인 모든 문장들이 모두 페아노 공리계나 ZF집합론처럼 어떤 공리들을 통해 나타낼 수 있다는 입장이다. 즉, 모든 수학의 정리들은 어떤 공리계로부터 유한한 길이로 증명할 수 있다는 입장이었다. 이를 '유한주의'나 '형식주의'라고 한다. 당대의 수학자들은 페아노 공리계나 ZF 공리계를 바탕으로 유한주의가 가능할 것이라고 기대했고, 이를 위해서 힘을 쏟았다. 그러나 힐버트의 꿈은 한명의 초신성에 의해서 박살나게 된다.

 

 학부에서 물리학을 전공하던 괴델은 지금까지 언급한 작업들을 보고 흥미를 두었었다. 그리하여 그는 수학연구를 하기 시작했다. 그리고 그는 엄청난 결과를 낳게 된다.

 

 1929년, 23살에 괴델은 일차논리학에서의 '완전성 정리'를 증명하게 된다. 이는 '증명가능하다'라는 개념과 '참이다'라는 개념이 서로 같다는 정리이다. 우리의 주제와는 좀 멀리있지만 논리학에서는 이것이 매우 중요한 정리인데, 이 정리를 바탕으로 논리학의 모든 개념들이 성립하게 된다. 논리학에는 증명을 다루는 증명론, 참의 개념을 다루는 모형론이 있는데, 이들의 정리들이 안전하게 보증될 수 있는 계단을 마련한 것이다. 또한, 완전성 정리를 바탕으로 논리학에서 매우 중요한 compactness를 증명할 수 있다. 이는 엄청나게 강력한 힘을 지니는데, 이를 바탕으로 비표준해석학을 구성할 수 있고, 수학적 모형들을 논리학의 언어로 환원하여 연구할 수 있게 된다. 괴델의 정리가 없었으면, 현대 논리학의 역사는 없었다는 것에 모든 논리학자들이 동의하리라 생각한다. 괴델은 이에 멈추지 않고 또 다른, 더 강력한 정리를 증명한다.

 

 1931년, 25살의 괴델은 박사학위 논문으로 '불완전성 정리'를 발표하게 된다. 그의 발표로 모든 수학계가 발칵 뒤집히게 되었는데, 이 정리는 당대의 유한주의를 완전히 박살내버렸기 때문이다. 괴델은 페아노 공리계가 완전하지 않음을 보였다. 페아노 공리계는 자연수 언어로 이루어져 있는 어떤 문장에 대해, 그 문장을 증명할 수도 반증할 수도 없다. 더욱이, 페아노 공리계는 스스로 공리계 자신에 모순이 없다는 것을 증명할 수 없다. 괴델의 정리의 함축은 여기서 멈추지 않았는데, 괴델의 정리는 더욱 나아가서 "자연수에서 참인 문장들의 집합은 공리화할 수 없다"는 것을 보이게 되었다. 즉, 페아노 공리계는 자연수에서 참인 모든 문장들을 모두 포착할 수는 없다. 더욱 일반적인 경우에서, 어떤 공리계가 오더라도 그 공리계는 자연수의 참인 모든 문장을 포착할 수는 없다. 이것이 괴델정리의 함축이었다.

 

 괴델은 힐버트를 정면에서 반박한 셈인데, 첫째로 수학적 공리계가 모든 수학적 참의 개념을 보장할 수 없고(즉, 참인 문장이지만 흥미롭게도 그에 대한 증명이 존재하지 않음), 또한 페아노 공리계가 스스로 무모순을 증명할 수 없다는 것을 보였기 때문이다. 괴델의 정리는 흥미롭게도, 페아노 공리계뿐만 아니라 ZF 집합론에도 이것이 똑같다는 것을 보였다. 즉, 집합론 역시 집합론에서 주어지는 어떤 문장을 증명도 반증할 수 없고, 또한 스스로의 무모순성을 증명할 수도 없다. 이렇게 힐버트의 꿈은 완전히 무너졌다.

 

 여담으로 페아노 공리계의 무모순성은 페아노 공리계 밖에서 증명될 수 있다. 겐첸이 이를 증명했고, 그는 증명의 길이를 무한하게 설정함으로써 페아노 공리계의 무모순성을 증명했다ㅡ그러나 상식적으로 우리가 증명이 존재한다고 말할 때, 이는 유한한 길이의 증명을 말하는 것이니 이는 어떤 의미에서는 비직관적이다ㅡ.

 

 

 이제부터 계산이론의 역사가 발발한다. 계산이론의 모형은 괴델의 불완전성 정리에서 찾을 수 있다. 괴델은 페아노 공리계의 불완전성을 증명하기 위해서 매우 흥미로운 작업들을 했다. 계산이론의 언어로 말하자면, 불완전성 정리는 '자연수의 참인 문장들을 나타낼 수 있는 알고리즘이 존재하지 않는다(즉 공리화불가능)'를 말한다. 괴델은 논리학의 언어를 코드화했고, 페아노 공리계를 코드화해서, 일반적인 케이스에서 그런 알고리즘이 없다는 것을 밝혔다.

 

 괴델은 정말 천재였다. 1931년에는 컴퓨터도 없었던 시대이고, 암호학이라는 개념이 수학적으로 성립하지 않던 시기였다(매트릭스처럼 수로 암호화된). 현재는 컴퓨터학과에 재학하거나 정수론 후반부를 수강하는 학생이라면 알게 되는 개념이지만, 당시에 누구도 '코딩'이라는 개념을 가지고 있지 않았다. 1931년은 정말로 그런 시대였다. 괴델은 그런 시대에 수학적 기호들을 수로 코딩하는 방식을 떠올렸고, 그 방식을 바탕으로 논리학의 언어를 수로 환원하였고, 그를 통해 공리계 일반을 수로 표현할 수 있었다. 괴델은 수학적 언어를 수로 환원하고, 그것들간의 기묘한 관계를 만들어냈다. 수학적 대상들을 아주 기초적인 함수들로부터 나타내는 방식을 만들었다. 현대적 방식으로 말하자면, 그는 +1 함수, 언제나 0을 내놓는 상수함수, 그리고 동일성함수와 합성함수, 재귀함수를 바탕으로 수학적 언어를 재구성했다. 괴델의 불완전성의 정리는 이 개념들을 모두 포함하고 있었다. 이러한 개념들은 22살의 튜링을 자극하였고, 발전되어 비로소 계산이론이라는 학문을 성립시키게 했다.

 

 괴델이 알고리즘에 대한 수학적 정의를 내린 것은 아니었다. 그는 대신에 수학적 언어를 코딩하고, 그것들에 관한 기초적인 함수들을 구성했다. 튜링은 괴델의 논문을 보면서 이에 대한 아이디어를 확장해서 튜링머신이라는 개념을 제창했고 이를 통해 알고리즘이라는 개념이 수학적으로 정의되었다. 또한 그는 흥미로운 개념을 제시했는데, 바로 모든 알고리즘을 계산하는 알고리즘에 대한 개념이었다. 현재 밝혀졌다시피 실제로 그런 알고리즘이 존재함이 후대에 증명되었다. 이는 매우 중요한데, 바로 컴퓨터의 개념을 성립시키기 때문이다. 컴퓨터에는 엄청난 수의 알고리즘이 있고, 어떤 명령이 주어졌을 때 어떤 알고리즘에 들어가 명령을 수행해야만 한다. 이것이 알고리즘에 대한 알고리즘의 한 사례인데, 이것의 존재성뿐만 아니라 '모든' 알고리즘을 계산하는 알고리즘의 존재성이 현재 밝혀졌다. 튜링이 직접한 것은 아니지만, 튜링은 이에 대한 개념을 제시했다.

 

 흥미롭게도, 괴델은 자신이 불완전성 정리에 사용했던 함수들이 원초적인 의미에서 '계산가능하다'라고 언급했었는데, 이것이 조금 더 발전된 개념ㅡrecursive functionsㅡ이 튜링머신에 의해 계산가능한 함수들과 정확히 일치한다. 더욱 흥미로운 것은, 컴과에서 배우는 모든 알고리즘의 개념들이 튜링머신에 의해 계산되고, 서로가 서로 같은 것을 계산할 수 있다ㅡ정확히는 튜링머신과 같은 것을 계산하지 않으면 그 알고리즘의 개념은 폐기해야 한다ㅡ.

 

 

 이렇게 해서 계산이론의 아주 기초적인 역사가 출발하게 되었다. 그 후에 이런 바탕으로 church, kleene, post 등의 학자들에 의해 계속해서 발전하였고, 현대까지 수리논리학의 주요한 분야로서 존재하고 있다.

 

 

 개인적으로는 괴델이 정말 모든 걸 해놓은 것 같다. 물론 알고리즘의 정의를 내린 것은 튜링이지만, 수리논리학을 발전시킨 것은 후대의 사람들이지만, 그것을 가능하게 모든 흔적을 만들어놓은 것은 괴델이기 때문이다. 괴델의 완전성 정리는 모형론을 성립하게 하였고ㅡ물론 후에 Henkin이 세련된 증명방식을 제시했지만, 처음 증명한 것은 괴델이다ㅡ, 불완전성 정리는 튜링에게 영감을 주어서 계산이론을 만들어내게 하였다. 청년 괴델은 23살, 25살에 각각 이것들을 증명했고, 역사 끝까지 남을 업적을 만들어냈다.