스티븐 클리니(Stephen Cole Kleene)

스티븐 콜 클리니는 1909년 미국 코네티컷주 하트퍼드에서 태어났습니다. 그가 프린스턴 대학원에 들어간 1930년 무렵, '기계적으로 계산할 수 있다'는 말은 아직 정확한 뜻이 없었습니다. 스승 처치는 함수⁠(function)⁠만으로 이루어진 람다 계산⁠(lambda calculus)⁠을 만들었지만, 그 안에서 뺄셈 같은 간단한 함수조차 적을 수 있는지 분명하지 않았습니다. 클리니는 람다 계산으로 앞의 수를 구하는 함수를 적는 방법을 찾아냈고, 그 뒤 수많은 함수를 차례로 적어 보이며 람다 계산이 생각보다 훨씬 많은 것을 계산한다는 것을 보였습니다. 처치가 "계산할 수 있는 함수란 람다 계산으로 적을 수 있는 함수"라는 제안에 이른 데에는 이 작업이 큰 몫을 했습니다.

나이 세 ·

그는 1934년 박사 학위를 받았고, 이듬해 동료 바클리 로서와 함께 처치의 원래 논리 체계에 모순이 있음을 보였습니다. 처치의 체계에서 살아남은 것은 논리를 떼어 낸 람다 계산뿐이었습니다. 1934년 프린스턴에서 괴델이 한 강의를 받아 적은 것도 클리니와 로서였고, 그 강의의 재귀 함수 정의는 클리니의 평생 주제가 되었습니다. 1936년 그는 일반 재귀 함수와 람다 계산으로 적을 수 있는 함수가 정확히 같다는 것을 증명했고, 같은 해 튜링의 기계까지 같은 함수들을 계산한다는 것이 곧 밝혀졌습니다. 서로 다른 세 정의가 한곳에 모인 것이 처치–튜링 논제⁠(Church–Turing thesis)⁠를 믿게 하는 가장 큰 근거가 되었고, '처치의 논제'나 '처치–튜링 논제'라는 이름을 널리 쓰게 한 사람도 클리니입니다.

1935년부터 그는 위스콘신 대학 매디슨에서 가르쳤고, 2차 세계대전 동안에는 해군에서 항법을 가르쳤습니다. 1945년에는 직관주의⁠(intuitionism)⁠ 산술의 증명마다 그것을 실현하는 계산을 짝지어 주는 '실현 가능성⁠(realizability)⁠' 해석을 내놓아, 증명을 만들어 건네는 방법으로 읽는 브라우어르의 생각에 계산의 뜻을 주었습니다. 1952년 책 『메타수학 입문』은 재귀 함수 이론과 증명론⁠(proof theory)⁠을 한 권에 모은 교과서로 한 세대의 논리학자를 길렀습니다.

그의 이름이 가장 널리 퍼진 것은 뜻밖의 경로를 통해서였습니다. 1951년 여름 랜드 연구소에서 그는 맥컬러와 피츠의 신경망 모형이 어떤 입력의 흐름을 알아볼 수 있는지를 분석했습니다. 답을 적으려고 그는 '이어 붙이기', '또는', 그리고 '0번 이상 되풀이'를 뜻하는 별표 $*$로 이루어진 식을 만들었습니다. 이것이 정규 표현식이고, 그의 정리는 이런 식으로 적을 수 있는 입력의 모임이 정확히 유한 오토마톤⁠(finite automaton)⁠이 알아보는 모임이라는 것입니다. 이 결과는 1956년 섀넌과 매카시가 엮은 『오토마타 연구』에 실렸고, 1960년대 말 켄 톰프슨이 문서 편집기에 정규 표현식 검색을 넣으면서 오늘날 거의 모든 프로그래밍 언어와 편집기의 기능이 되었습니다. 별표는 반환⁠(semiring)⁠의 이론에서도 '닫힘'이라는 이름으로 쓰입니다.

그는 1969년부터 1974년까지 인문과학대 학장을 지냈고, 일흔이 넘어서까지 암벽을 오른 등산가였습니다. 1990년 미국 국가 과학 훈장을 받았고, 1994년 매디슨에서 세상을 떠났습니다.

이어지는 곳. 계산 가능성⁠(computability)⁠의 세 정의가 한곳에 모인 이야기는 처치–튜링 논제, 람다 계산, 튜링 기계⁠(Turing machine)⁠에서, 그 한계는 정지 문제⁠(halting problem)⁠에서 볼 수 있습니다. 정규 표현식과 오토마타는 정규 표현식과 유한 오토마톤에, 별표가 최단 경로⁠(shortest path)⁠와 경우의 수⁠(number of cases)⁠를 한 계산으로 묶는 모습은 반환에 있습니다.

관계.

• 스승 알론조 처치 — 프린스턴에서 처치의 지도로 박사 학위를 받았고, 람다 계산으로 어떤 함수를 계산할 수 있는지를 밝혀 처치가 '계산할 수 있다'를 정의하는 데 힘을 보탰습니다.
• 영향을 받음 쿠르트 괴델 — 1934년 괴델이 프린스턴에서 한 강의를 로서와 함께 받아 적었고, 그 강의에 나온 재귀 함수의 정의를 자기 연구의 출발점으로 삼았습니다.
• 영향을 받음 워런 맥컬러 — 1951년 랜드 연구소에서 맥컬러와 피츠의 신경망 모형이 무엇을 알아볼 수 있는지 분석하다 정규 표현식을 만들었습니다.

연표.

• 1909년 코네티컷주 하트퍼드에서 태어나다
• 1930년 애머스트 칼리지를 졸업하다
• 1934년 프린스턴에서 처치의 지도로 박사 학위를 받다
• 1935년 로서와 함께 처치의 원래 논리 체계에 모순이 있음을 보이다
• 1935년 위스콘신 대학 매디슨의 강사가 되다
• 1936년 일반 재귀 함수와 λ-정의 가능성의 동치를 보이다
• 1942년 해군에서 항법 교관으로 복무하기 시작하다(1945년까지)
• 1945년 직관주의 산술의 실현 가능성 해석을 내놓다
• 1951년 랜드 연구소에서 신경망과 유한 오토마톤을 분석하다
• 1952년 『메타수학 입문』을 내다
• 1956년 「신경망과 유한 오토마타의 사건⁠(event)⁠ 표현」이 『오토마타 연구』에 실리다
• 1969년 위스콘신 대학 인문과학대 학장이 되다(1974년까지)
• 1990년 미국 국가 과학 훈장을 받다
• 1994년 매디슨에서 세상을 떠나다