C 언어와 유닉스(Unix)의 아버지, 데니스 리치의 잃어버린 논문 발견!

데니스 리치(Dennis Ritchie)는 학위 논문 제출을 위한 제본 비용(Binding Fee)을 지불하지 않아 박사 학위를 받지 못했다. 당시 하버드(Harvard) 대학교의 규정에 따르면, 도서관에 제본된 논문을 제출해야 학위가 인정되었다. 리치는 벨 연구소(Bell Labs)에 이미 취업한 상태였고, 학위보다는 실용적인 연구(Practical Research)에 더 집중했다.

리치의 논문은 루프 프로그램(Loop Programs)을 통해 계산 복잡성(Computational Complexity)을 분석하는 방법을 제시한다. 루프 프로그램은 변수 할당, 증가, 이동 등의 간단한 연산만을 허용하며, 루프의 중첩 정도를 통해 계산 시간을 측정한다. 이는 당시 복잡한 수학적 표기법(Mathematical Notation)을 사용하던 연구에 비해 직관적이고 이해하기 쉬운 모델을 제공했다.

1960년대 초, 계산 가능성(Computability)의 한계를 넘어 계산 복잡성(Computational Complexity)에 대한 연구가 시작되었다. 괴델(Gödel)과 튜링(Turing)의 연구를 통해 계산 가능한 것과 불가능한 것이 밝혀진 후, 연구자들은 계산의 효율성에 주목했다. 리치의 논문은 이러한 흐름 속에서 계산의 어려움(Computational Difficulty)을 분석하는 데 기여했다.

리치는 하버드(Harvard) 대학교 동료였던 알버트 마이어(Albert Meyer)와 함께 루프 프로그램(Loop Programs)에 대한 연구를 진행했다. 두 사람은 1967년 ACM에 "루프 프로그램의 복잡성(The Complexity of Loop Programs)"이라는 논문을 발표했다. 마이어는 리치의 루프 프로그램(Loop Programs)이 계산 복잡성(Computational Complexity) 연구에 중요한 기여를 했다고 평가했다.