컴퓨터 과학자로서의 삶

젊은 시절의 마이클 래빈​‡​

마이클 래빈(Michael Rabin)은 1931년 9월 1일에 독일의 브레슬라우Breslau(현재는 폴란드에 속해있다.)에서 태어났다. 그의 부친은 랍비였고 현지의 유대인 신학교 교장을 맡고 있었다. 독일의 분위기가 심상치 않음을 느낀 부친은 1935년에 가족을 데리고 팔레스타인으로 이주했다. 현재 이스라엘의 하이파 지역이다.

생물학자를 꿈꾸던 그는 우연한 기회에 수학적 재능을 드러냈다.

내가 11살인가 12살인가 되던 때였습니다. 수업 시간에 버릇없이 굴었다고 교실 밖으로 쫓겨났습니다. 그런데 복도에 나와 보니까 9학년이던 학생 두 명이 역시 교실에서 쫓겨나 있었습니다… 그들 앞에 가서 물었습니다. “뭐 하고 있어요?” 그들은 기하 문제를 못 풀어서 밖에 나와 있다고 말했습니다. 풀어야 할 문제가 여러 개 있었는데 두 사람은 원이 두 개 그려진 문제를 놓고 낑낑대고 있었습니다. 나는 그 당시 기하학이 뭔지도 몰랐지만 바로 답을 생각해냈고 그들에게 설명해주었습니다.​2​

수학에서 재미를 발견한 그는 수학자가 되기로 마음먹었다. 유대 신학을 공부하길 바라던 부친을 설득했고 2년 만에 허락을 받아 하이파에서 가장 좋은 이과 계열 고등학교에 진학했다. 그곳에서 그는 훌륭한 수학 선생님인 엘리샤 네타냐후Elisha Netanyahu​§​를 만났고 정규 교과 과정을 넘어서 고급 수준의 수학 공부를 했다.

그는 예정보다 일찍 고등학교를 졸업했다. 그 이유는 이스라엘에서 독립 전쟁​¶​이 벌어졌기 때문이었다. 같은 학년의 학생들이 모두 징집되었다. 그는 통신과에 배치되었고 기초적인 암호 시스템을 담당했다. 복무 중에도 그는 수학 관련 책을 읽으며 꾸준히 수학 공부를 했다.

독립 전쟁이 끝난 후 그는 2년의 의무 복무를 마저 마쳐야 했다. 군 생활이 너무 지루했던 그는 옛 고등학교 수학 선생님에게 ‘빨리 대학에 갈 방법이 없겠냐’는 편지를 보냈다. 엘리샤 네타냐후는 히브리 대학의 수학 교수이던 에이브래햄 프랜클Abraham Fraenkel에게 편지를 써서, 좋은 청년이 있는데 현재 군대에서 썩고 있다며 더 이상 전쟁도 없는 상황이니 일찍 제대시켜 대학 진학을 시켰으면 좋겠다는 의견을 피력했다. 프랜클 교수과 면담한 래빈은 군대를 벗어날 수 있었다.​2​

1950년에 히브리 대학교 수학과에 입학한 래빈은 2학년 과정부터 수업을 들었다. 이미 그는 1학년 과정에서 들을 것이 없었기 때문이었다. 1953년에 그는 논문을 작성하고 석사로 졸업했다. 그가 작성한 논문은 독일의 저명한 수학자였던 에미 뇌터Emmy Noether가 제시했던 미해결 문제에 관한 답이었다.

래빈은 미국에서 공부를 이어가기로 마음먹었다. 그래서 프랜클 교수의 도움으로 펜실베이니아 대학교 수학과 박사 과정에 입학했지만 그가 원하던 곳은 따로 있었다. 당시 미국에서 수학 연구의 최고봉에 있던 프린스턴 대학교였다.

컴퓨팅 연구의 중심은 프린스턴임을 알고 있었습니다. 나는 그곳에 가야만 했습니다… 그 당시에는 얼마나 경쟁이 치열한지 깨닫지 못했습니다… 후에 내가 프린스턴의 교수가 되었을 때 누군가 나에게 말해주더군요. 당시에 그가 입학 심사 위원회에 있었는데 나의 석사 논문이 큰 역할을 했다구요.​2​

그는 프린스턴 대학교 수학과 박사 과정의 문을 두드렸고 일 년에 13명으로 제한되어 있던 신입 대학원생에 포함되었다. 알론조 처치Alonzo Church 교수 밑에서 박사 과정을 시작한 그는 2년 만에 박사 학위를 받는 기록을 세웠다. 이때가 1957년이었다.

젊은 시절의 데이나 스콧​#​

데이나 스튜어트 스콧(Dana Stewart Scott)은 1932년 10월 11일에 미국 캘리포니아 버클리에서 태어났다. 그는 어린 시절에 부모의 잦은 이혼으로 여러 번 이사해야 했는데 아이러니하게도 그가 수학에 관심을 가지게 되는 결과를 가져왔다. 어머니와 함께 살았던 그는, 어머니가 세 번째 결혼을 하면서 캘리포니아 치코Chico에 있는 고등학교로 진학하게 되었다. 음악을 좋아했던 그는 학교 밴드부에서 활동했는데 밴드부 선생님은 그의 열정을 보고는 책을 한 권 건네주었다.

그 선생님은 데이튼 클래런스 밀러Dayton Clarence Miller라는 사람이 쓴 <음악적 소리에 관한 과학The Science of Musical Sounds>이라는 책을 가지고 있었습니다… 나는 그 책에 완전히 빠졌습니다… 하지만 문제가 있었습니다. 그 책은 미적분학을 포함해서 수학을 많이 포함하고 있었습니다. 그래서 나는 혼자서 미적분학을 공부해야 했습니다.​3​

그가 고등학교 2학년이 되었을 때 양아버지가 직장을 옮기게 되어 가족이 모두 새크라멘토로 이사가게 되었다. 스콧은 치코에서 사귀었던 친구들과 헤어지게 되어 매우 슬퍼했다. 하지만 새크라멘토의 고등학교에 등교하자마자 생각이 바뀌었다. 치코의 고등학교보다 좋았고 무엇보다도 수학 시간이 아주 마음에 들었다. 아울러 두 가지로 인해서 그의 인생은 큰 영향을 받게 된다.

새크라멘토에는 캘리포니아주의 주립 도서관이 있었습니다. 그곳에서 나는 독일의 유명한 과학자인 헤르만 폰 헬름홀츠Hermann von Helmholtz가 쓴 음악 이론 책을 발견했습니다…. 그 책에서 푸리에 분석을 알게 되었고… 로그logarithm도 접하게 되었습니다.​3​

거기에 더해서 새크라멘토에서는 캘리포니아 대학교 버클리에 입학하기가 쉬웠다. 그래서 수학에 대한 열정을 가득 담은 채로 1950년에 스콧은 버클리에 입학했다.

당시 버클리의 수학과에는 논리학의 대가이던 알프레드 타르스키Alfred Tarski가 있었다. 스콧은 학부생이었지만 타르스키의 연구 그룹에 참여하게 된다. 여기에서도 역시 도서관이 계기를 만들어냈다.

1951년에 나는 생활비를 벌기 위해서 학교 도서관의 정기간행물실에서 일했습니다. 그 시절은 지금처럼 정기간행물이 도서관을 망하게 만들 정도는 아니어서 그렇게 종류가 많지는 않았습니다. 하지만 계속 쌓여나가기 때문에 세심하게 정리되어야 했죠. 그래서 그 일을 위해 학생을 고용했습니다.

정기간행물 더미 속에서 나는 기호 논리학 논문지Journal of Symbolic Logic라는 걸 발견했는데 펼쳐보니 내가 이해할 수 있는 글이 없더군요. 그때 대학교 2학년에 불과했으니까요. 하지만 얀 칼리츠키Jan Kalicki라는 사람이 쓴 논문은 진리표truth table에 관한 것이었고 그리 어렵지 않았습니다. 그래서 그 논문은 읽을 수 있었습니다.

그런데 2학기에 방정식 이론 과목의 강사가 얀 칼리츠키였습니다. 그래서 그에게 다가가서 “당신의 논문을 읽었습니다”라고 말했더니 아주 좋아했습니다. 그는 이런 쪽으로 함께 논의해보자고 제안했고 우리는 좋은 친구가 되었습니다… 우리는 방정식 이론에 관하여 많은 것들을 새로 발견했고 타르스키 교수는 큰 관심을 보였습니다.​3​

학부 2학년 시절부터 본격적인 수학 연구에 발을 담근 그는 1954년에 자연스럽게 버클리의 대학원에 진학했고 타르스키 교수 밑에서 연구를 진행했다. 하지만 타르스키 교수가 시킨 원고 교정일을 게을리하다가 타르스키 교수의 노여움을 사게 되었고 그의 연구실에서 쫓겨나는 신세가 되었다. 천만다행으로 마침 버클리에서 안식년을 보내기 위해 방문 중이었던 프린스턴 대학교의 노먼 스틴로드Norman Steenrod 교수가 그를 좋게 보았고 스틴로드 교수의 추천으로 프린스턴 대학교 수학과 대학원에 입학하게 된다.

그는 알론조 처치 교수 밑에서 독자적으로 연구를 진행했다. 처치 교수는 학생이 주제를 정할 때는 함께 했지만 연구 자체에는 크게 관여하지 않는 스타일이었다. 그는 버클리 시절에 타르스키 교수와 논의했던 주제로 박사 논문을 쓰고 1958년에 학위를 받았다. 그러니까 1957년 여름에 캠퍼스를 방문한 IBM 직원으로부터 여름 인턴십을 제안받았을 때는 혼자서 열심히 박사 논문을 준비하고 있던 와중이었다.

1957년 여름에 래빈과 스콧은 뉴욕시 외곽에 위치한, IBM의 임시 연구소 건물에서 오토마타automata에 관한 작업을 진행했다. 새로운 개념을 제시한다기보다는, 기존의 연구들을 정리하면서 새로운 시각을 보태려는 시도였다. 그런데 이 과정에서 비결정적 오토마타nondeterministic automata가 튀어나왔다.

논리학자였던 존 마이힐이 오토마타에 관한 그의 연구를 프린스턴에서 발표한 지 얼마 되지 않았을 때였습니다. 마이힐은 시카고 대학교에서 초기 연구를 했고 특히나 어닐 너로드Anil Nerode의 영향을 받았더랬죠.

램 저택, 그러니까 IBM 센터에 도착한 래빈과 나는 뭘 해야 할지 몰랐습니다. 그래서 이렇게 말했죠. “글쎄요. 오토마타에 관한 (마이힐의) 작업을 검토하면서 오토마타에 대해 좀 생각해봐야 하지 않을까요?” 우리 생각에는 모델 이론model theory 관점에서 좀 더 들여다보고 구조에 있어서도 좀 더 대수적 구조algebraic structure로 접근해 볼 수 있을 것 같았습니다. 그렇게 해서 시작된 일이었습니다. 존 마이힐의 영향을 받았던 거죠….

하지만 우리가 왜 비결정적 오토마타를 생각해냈는지는 잘 기억나지 않는군요. 지금 와서 내가 할 수 있는 말이라고는, 어쩌다 보니 그것으로 인해 우리의 삶이 더 편해졌다는 겁니다.​3​

래빈과 스콧은 같은 지도교수 밑에서 박사학위를 받았으나 함께 연구를 진행한 적은 없었다. 1957년의 한여름 밤 꿈만 같은 협업이 끝난 후에 그들은 각자의 길을 걸어갔고 후에 버클리에서 잠시 함께 시간을 보낸 적은 있었으나 공동 연구를 하지는 않았다.​**​

1958년 여름에 래빈은 다시 그 으시시한 대저택을 찾아왔다. 스콧은 함께 하지 않았다. 외롭게 건물에 들어선 래빈 앞에 의외의 인물이 나타났다. 다름 아닌 존 매카시였다. 이제 막 MIT의 교수로 자리를 옮겼던 매카시는 여름을 IBM에서 보내기로 마음먹은 상태였다. 매카시는 래빈에게 수수께끼 같은 문제를 하나 냈고, 래빈은 그 답을 찾는 과정에서 계산복잡도Computational complexity라는 새로운 연구 분야를 만들었다.

1959년에 그는 고향인 예루살렘으로 돌아가 히브리 대학교의 수학과 교수가 되었고 논리학과 모델이론 및 계산에 관한 연구를 이어갔다.

1960년에 래빈은 에드워드 무어Edward Moore의 초청을 받아 미국 벨연구소에서 여름을 보냈다. 이때 그는 확률적 오토마타probailistic automata를 생각해냈다. 오토마타 내의 각 상태에서 다음 상태로의 전이를 결정할 때 확률이 개입하는 오토마타였다. 확률적 오토마타는 기존의 오토마타에 비해 더 적은 수의 내부 상태로 같은 일을 할 수 있었다.

논리학과 오토마타에 대한 열정을 계속 이어간 래빈은 1969년에 ω-오토마타와 관련된 결과물을 발표했다. 이것은 무한이 이어지는 입력에 대해 참/거짓을 결정할 수 있는decidable 오토마타이다.

래빈은 1975년에 히브리 대학교의 학술 총장 임기를 마친 후에 미국으로 건너와 MIT에서 방문 교수로 근무했다. 여기서 그는 개리 밀러Gary Miller를 만나게 된다. 밀러는 어떤 숫자가 소수prime인지를 판별하는 방법을 고안해냈다. 그의 방법은 다항 시간polynomial time 안에 종료된다는 장점을 가지고 있었으나 결정적인 약점을 가지고 있었는데, 아직 증명되지 않은 리만 가설에 기반하고 있었다는 것이었다. 따라서 보기에는 완벽해 보일지 모르지만 리만 가설이 거짓으로 판명되는 순간, 밀러의 방법도 더 이상 신뢰할 수 없게 되는 한계를 가졌다. 래빈은 리만 가설이 필요 없는 새로운 알고리듬을 고안해냈다. 밀러-래빈 소수성 검사Miller-Rabin primality test라고 불리는 이 방법은 무작위 알고리듬randomized algorithm을 사용했는데 어떤 정수가 소수인지를 빨리 판별할 수 있어서, 컴퓨터를 이용한 암호가 현실화되는 데 크게 공헌했다.

무작위 알고리듬을 처음 발견한 이가 래빈은 아니었으나 그가 소수성 검사에 적용한 후로 무작위 알고리듬은 컴퓨터 이론 연구에서 중요한 영역으로 자리 잡게 되었다. 래빈도 무작위 알고리듬을 적극적으로 활용했다. 1981년에는 비잔틴 문제Byzantine agreement에 무작위 알고리듬을 적용했고, 이 업적으로 2015년에는 다익스트라 상을 받았다.

래빈의 연구 열정은 나이와 상관없었다. 그는 70대 후반이던 2008년에는 스튜어트 쉬버Stuart Shieber, 데이비드 팍스David Parks, 크리스 소프Chris Thorpe와 함께 보안에 관한 논문을 발표했다. 이것은 온라인 경매 시스템에서 참가자의 개인정보를 보호하면서도 공정한 경매가 이루어지도록 하는 방법을 담고 있다.

데이나 스콧은 박사 학위를 받기 전에 잠시 프린스턴 대학교 고등연구원에서 컴퓨터 프로그래밍을 작성하기도 했다.​††​ 1958년에 박사 학위를 받은 후 시카고 대학교 수학과 강사로 임용된 그는 캘리포니아 버클리, 스탠퍼드 대학교 등으로 자리를 옮기면서 논리학에 관한 중요한 연구 업적을 쌓았다.

그는 1968년에서 1969년 사이에 안식년을 맞이하여 네덜란드로 건너가 암스테르담 대학교의 방문 교수로 지냈다. 이 시기에 패트릭 수피스Patrick Suppes 교수를 대신해서 IFIP WG 2.2에서도 활동했는데 그는 크리스토퍼 스트레이치Christopher Strachey 교수를 만나게 된다.

거기서 스트레이치를 알게 되었는데 나는 프로그래밍 언어 설계에 관한 아주 많은 문제점들을 들었고 특히나 당시 알골 언어 개발과 관련된 모든 논쟁들을 알게 되었습니다. 이 모든 것을 듣고 나서 스트레이치가 추진하려는 방향을 알게 된 후에 나는 컴퓨터 언어에 대한 그의 관점에 아주 많이 끌렸습니다.​3​

안식년을 마침과 동시에 스탠퍼드에서 프린스턴으로 자리를 옮긴 스콧은 첫 학기에 휴가를 받아서 런던으로 날아갔고 옥스퍼드 대학교에 있던 스트레이치 교수를 찾아갔다.

스트레이치 교수가 하고 싶어 했던 일은 프로그래밍 언어의 의미semantics를 수학적으로 표현해서 검증하는 것이었다. 프로그래밍 언어의 문법syntax은 이미 자동으로 검사를 할 방법이 있었다. 하지만 의미semantics는 아직 그 수준에 이르지 못했다. 스콧은 스트레이치와 함께 표시적 의미론Denotational semantics이라는 방법을 만들어냈다. 이 방법은 컴퓨터 프로그램을 수학적 표기법으로 대치한 후에 그 프로그램의 의미를 수학적으로 추적할 수 있게 해주었다.

스콧은 결국 프린스턴을 떠나 1972년부터 1981년까지 옥스퍼드에서 수학과 교수로 재직하며 왕성한 연구 활동을 지속했고 1981년에 다시 미국으로 돌아와 카네기 멜런 대학교 컴퓨터 과학과 교수로 활동했다.

1 2 3 4 5