컴퓨터 과학자로서의 삶

젊은 날의 유리스 하트마니스​†​

유리스 하트마니스(Juris Hartmanis)는 1928년 7월 5일에 유럽의 라트비아에서 태어났다. 그의 부친은 철도 고등학교를 졸업한 후에 직업 군인이 되기 위해서 러시아 군대에 입대했다. 제1차 세계대전에 참전했다가 감옥 생활을 하기도 했으나 전쟁이 끝난 후 라트비아가 독립했을 때 고국으로 돌아와 장교로 복무했으며 상당한 지위에 이르렀다. 그래서 하트마니스가 태어났을 때 그의 가족은 방이 38개에 달하는 대저택에 살고 있었다. 하지만 그의 부친은 제2차 세계대전 때 러시아 군에게 붙잡혀 포로가 된 후 곧 사망했다.​3​

부친이 사망한 후에 하트마니스가 살던 저택은 러시아군의 손에 넘어갔다가 다시 독일군의 손에 넘어가는 상황을 겪었다. 독일군과 우호적인 관계였던 하트마니스 가족은 독일군이 다시 패퇴할 때 함께 독일로 넘어갔다. 마르부르크Marbug에 정착한 그는 그곳에서 고등학교를 마쳤고 마르부르크 대학교에서 물리학을 공부했다. 그러다가 미국 이민 허가를 받게 되어 3학년을 마치지 않고 미국 켄자스시티로 이주했다.

공부를 계속 이어가고 싶었던 하트마니스는 마르부르크 대학교에서 정식으로 졸업하지 않았으므로 학부 졸업장을 가지고 있지 않았다. 하지만 그에게는 수강한 과목들이 기록된 일종의 성적 증명서가 있었다. 그 서류를 들고 그는 켄자스시티 대학교의 문을 두드렸다.

그들(대학의 담당자)은 이렇게 말했습니다. “당신은 이러저러하게 많은 과목을 들었군요. 학부 졸업장을 받았어도 무방했겠습니다. 대학원에 입학하시죠.” 나는 속으로 생각했습니다. “이거 괜찮은데. 독일에서 2년 정도 대학교에 다녔는데 학사 학위를 가진 거라고?”
그런데 나는 물리학을 공부하고 싶었지만 안타깝게도 그곳은 대학원에 물리학과가 없었습니다. 대학 담당자들은 나에게 그곳의 수학과가 좋다고 말해주었다. “당신은 행복하게 수학을 공부할 겁니다.” 실제로 나는 수학을 공부해서 행복했습니다. 켄자스시티는 멋진 곳이었습니다.​3​

석사 학위를 받은 그는 박사에 도전했다. 그는 켄자스시티 대학교, 네브래스카 대학교, 캘리포니아 공과대학에 지원했다. 여전히 물리학에 대한 미련을 버리지 못했던 그였는데, 캘리포니아 공과대학에서 면접관은 그의 지원서를 보더니 이렇게 말했다.

“당신은 응용 수학자로군요.”

응용 수학에 관한 수업은 하나도 들은 적이 없었던 그였으나, 그런 평가 덕분에 캘리포니아 공과대학 수학과 박사 과정에 입학하게 된다. 그리고 4년 후에 박사 학위를 받은 그는, 코넬 대학교에서 강사로 일하기 시작했다.

그때 제너럴일렉트릭 사는 정보처리를 연구하는 부서를 신설하고 연구원을 찾아 유명 대학들을 방문하고 있었다. 그 부서의 책임을 맡은 딕 슈이 박사는 캘리포니아 공과대학을 방문했다가 유리스 하트마니스를 추천받았다. 그는 다시 코넬 대학교를 방문했고 하트마니스에게 입사 제안을 했다.

당시 하트마니스는 오하이오 대학교에서 제안한 조교수 자리를 수락한 상태여서 난색을 표했다. 슈이 박사는 단념하지 않았고 여름 방학 기간 동안이라도 잠시 와서 같이 일해보자고 제안했다. 그렇게 잠시 제너럴일렉트릭 연구소에서 시간을 보낸 후 그는 오하이오 대학교로 날아갔는데, 원래 계획대로 일이 풀리지 않았다. 고민에 빠진 그는, 여름 방학 기간 동안 제너럴일렉트릭 연구소에서 받았던 지적 자극을 잊지 못했고, 뉴욕 주로 돌아가 제너럴일렉트릭 연구소에 합류했다.

리처드 스턴즈(Richard Stearns)는 1936년 7월 5일에 뉴저지주 콜드웰에서 태어났다. 흥미롭게도 유리스 하트마니스와 생일이 같다.

그의 부모는 모두 화학을 전공했다. 아버지는 화학 박사였고 어머니는 스와스모어 대학Swarthmore college에서 화학과를 졸업했는데 유일한 여성이었다. 집안에 수학 관련 서적들이 있어서 스턴즈는 자연스럽게 그런 책을 접할 수 있었고 고등학교 때에는 수학에 더욱 흥미를 느끼게 되었다.

내성적이었던 그는 집에서 가까운 학부 중심의 남녀공학 대학에 진학할 생각이었으나 갑자기 부친의 직장 때문에 시카고로 이사를 가면서 생각이 바뀌게 된다. 그는 작은아버지의 권유로 칼튼 대학Carleton colledge에 입학했고 본격적으로 수학을 공부하기 시작했다.

2학년 학기가 끝나고 그는 여름 방학 동안 집에서 읽을 만한 수학책을 빌리기 위해 학교 도서관에 갔다. 그리고 그곳에서 그가 집은 책은, 폰 노이만과 모겐스턴이 쓴 <게임이론과 경제적 행동>​4​이었다.

정말로 인상적인 책이었습니다. 그러니까 아주 바닥에서부터 그들은 게임에 대한 모델을 만들어 나갔습니다. 나는 그것이야말로 수학이 따라야 하는 방법이라고 생각했습니다. 여러분은 최대한 현실 세계를 반영하겠다는 희망 아래, 자신의 모델을 주의 깊게 만들어야 하고 그런 후에 그것으로부터 작업을 해나가고 있는지 생각해 봐야 합니다. 나는 그 책에서 큰 깨달음을 얻었다고 느꼈습니다.​5​

학부를 우수한 성적으로 졸업한 스턴즈는 프린스턴 대학교 대학원 수학과에 진학했다. 프린스턴을 선택하게 된 동기는 칼튼 대학을 방문했던 존 케메니John Kemeny 교수​‡​가 프린스턴 대학교 수학과에 대해 엄청나게 좋게 말했기 때문이었다고 한다. 폰 노이만과 모겐스턴이 프린스턴 대학교 교수였던 점을 생각하면 스턴즈의 선택은 당연하다고 보인다.

프린스턴 대학교에서 스턴즈의 박사 논문 주제는 게임 이론이었다. 폰 노이만과 모겐스턴의 영향으로 프린스턴 대학교 구내 서점에는 게임 이론에 관한 책이 많았고, 스턴즈는 그 책들을 읽으면서 자연스럽게 게임 이론을 주제로 선택했다.​5​

이 시기에 제너럴일렉트릭 연구소가 그에게 등장한다. 인재 영입을 위해 전국을 누비던 채용팀은 하버드 대학교를 방문했다. 그런데 하버드 대학교 수학과 박사과정에 있던, 스턴즈의 친한 대학 친구가 여름 인턴에 지원했고 면접 중에 스턴즈를 언급했다. “그런데 말이죠. 여러분은 딕 스턴즈도 뽑고 싶어질 겁니다.” 그래서 여름 인턴에 전혀 관심도 없던 스턴즈에게 제안이 들어왔고 그는 덜컥 그 제안을 받아들였다.

그곳에서 일하는 방식은, 연구소 직원들이 “음, 자네가 뭔가 일을 하기는 해야 하니까… 여기에 자네가 붙잡고 할 만한 것이 있네”하고 제각각 제안하는 식이었습니다. 그중 하나가 하트마니스가 제안한 것이었습니다. 당시에 그는 <상태 할당 문제, 1>이라는 논문을 발표했습니다. 그는, “음, 잘 봐. 이건 유한 상태 기계에 관한 것이고 치환속성substitution property을 사용해서 쪼개는 거야”라고 말했습니다. 그가 “잘 봐”라고 말했기 때문에 나는 잘 봤습니다. 그리고 그 문제에 대해 더 많이 알기 위해 다른 예제들을 만들어봤습니다… 나는 MM-래티스lattice라고 불리는 방법을 떠올렸고… 그것은 <상태 할당 문제 2>라는 논문으로 이어졌습니다.​5​

학교로 돌아온 스턴즈는 논문 작성에 몰두했고, <측면 보상이 없는 삼자 협력 게임Three Person Cooperative Games without Side Payments>이라는 제목으로 박사 학위를 받았다. 마침 그때쯤 제너럴일렉트릭의 딕 슈이 박사가 그에게 전화를 걸어왔다. 여름 인턴을 또 할 생각이 있는지 묻자, 스턴즈는 “글쎄요. 졸업할 예정이라서요”라고 답했다. 그러자 슈이 박사는 바로 정규직 제안을 했고 스턴즈는 이를 받아들였다.

1960년 여름에 처음 시작된 하트마니스와 스턴즈의 인연은 1961년에 스턴즈가 제너럴일렉트릭 연구소에 정식으로 입사하면서 깊어졌다. 두 사람은 함께 연구를 진행해서 여러 논문과 책을 발표했고, 그중 하나가 그 유명한 <알고리듬의 계산 복잡도에 관하여>​6​이다. 그 시작은 클로드 섀넌의 정보 이론에서 비롯되었다.

섀넌의 작업에서 나는 처음으로 정보라는 추상적 존재의 동작을 지배하는, 정확하고 정량적인 법칙을 보았습니다.
어떤 문제에 대해서 해답을 구하는 데 필요한 계산이 얼마나 필요한지를 정하는 정량적 법칙, 그리고 그것을 측정하는 방법이 존재할까?
우리는 어떤 것이 정량적인지에 대한 질문에서부터 시작했습니다. “복수 개의 테이프를 가지는 기계가 한 개의 테이프를 가지는 기계보다 얼마나 더 좋을까? 복수 개의 테이프를 가지는 기계가 얼마나 더 빠를까?” 그때까지는 누구도 그런 질문을 던지지 않았습니다. 결국 우리가 다다른 질문은, “만약 튜링 기계를 수정한다면 튜링 기계에서 계산 시간이 얼마나 많이 바뀔까?”였습니다.​3​

두 사람은 알고리듬의 계산 복잡성computational complexity이라는 개념을 소개하면서, 서로 다른 계산들을 수행하는 데 있어 얼마나 많은 시간과 메모리가 필요한지에 따라 그 계산들을 여러 부류classes로 정의하였다. 어떤 문제는 간단한 절차만으로 해답을 얻을 수 있는 반면에, 어떤 것들은 매우 계산하기 어렵다. 그래서 두 사람은, 계산가능한computable 문제들이 고유한 복잡성complexity을 가지고 있다고 보았고, 얼마나 계산하기 어려운가에 따라 분류한 후 그들 간의 관계를 제시하였다.

이 외에도 두 사람이 함께한 연구 주제로는 오토마타, 계산 복잡도 뿐만 아니라 데이터베이스에서의 동시적concurrency 제어, 외판원 문제traveling salesman problem 등이 있었다.​5​

1965년에 하트마니스는 코넬 대학교로 자리를 옮겼다. 그는 새로 만들어진 컴퓨터 과학과를 맡아서 코넬 대학교가 컴퓨터 과학 분야에서 선도적인 자리를 차지하는 데 기여했다. 미국 정부의 위원회 및 각종 자문위원회에서 활동하기도 했던 그는, 평생을 일한 코넬 대학교 인근 자택에서 2022년 7월 29일에 세상을 떠났다.

스턴즈는 1978년에 제너럴일렉트릭을 떠나 뉴욕 주립대학교SUNY의 컴퓨터 과학과로 이직했다. 역시 여러 위원회에서 활동했던 그는 2000년에 은퇴했다.

1 2 3 4