기타 업적

스티븐 쿡은 수학자였지만 컴퓨터 과학과에서 평생을 보냈다. 따라서 컴퓨터 과학의 다른 영역과도 접점을 가지려 노력했다. 프로그래밍 의미론 연구와 병렬처리 연구가 대표적이다.

프로그래밍 의미론

프로그램의 의미를 자동으로 검증하려는 노력은 여러 가지 형태로 시도되어 왔다. 그중 공리적 의미론axiomatic semantics은 프로그램 코드 상의 각 명령어(혹은 블록)를 수학적 수식으로 표현한 후 수학적 추론을 적용하여 프로그램의 결과를 도출해 내는 방식이다. 그렇게 만들어 낸 결과는 어떤 수학적 수식으로 표현될 터인데 그것이 프로그램의 원하는 결과와 부합하는지를 따져보면 프로그램이 제대로 작성되었는지를 판단할 수 있다. 공리적 의미론은 로버트 플로이드​#​에서 시작되었고 토니 호어​**​에 의해 발전되었다.

공리적 의미론은 수학적 추론을 적용할 수 있다는 점에서는 매력적이지만 실제 프로그래밍 언어에 적용하기에는 제한이 많았다. 스티븐 쿡은 좀 더 현실에 가까운 프로그래밍 언어를 가정하고 공리적 의미론을 적용해 보았다.​7​ 그가 가정한 언어는 알골 언어와 유사한데, 블록문은 물론이고 조건문, 반복문, 프로시져 호출 등을 포함했으며 전역변수global variable를 허용했다.

그는 호어 트리플Hoare Triples 표기법을 사용했는데 자신이 모델링한 공리 시스템axiomatic system이 완전completeness하면서 건전함soundness을 증명했다. 여기서 건전함이란 어떤 수식이 문법 규칙에 의거하여 추론되었다면 의미적으로도 옳다는 것을 의미하며, 완전함이란 어떤 수식이 의미론적 규칙에 의해 추론되었다면 문법적으로도 참이라는 것을 의미한다.

병렬처리 회로 복잡도

1980년대에는 컴퓨터의 성능을 향상시키기 위한 방법의 하나로 병렬처리에 관한 관심이 높았다. 스티븐 쿡은 병렬처리의 복잡도에 주목했는데 특히 회로의 복잡도에 관심을 가졌다.

불 논리를 기반으로 하는 논리회로에서 덧셈 회로, 뺄셈 회로는 만들기가 어렵지 않다. 이에 비해 곱셈회로나 나눗셈 회로는 복잡하다. 그렇다면 회로의 복잡도는 어떻게 정량화할 수 있을까? 만약 회로의 기본 단위가 동일하다면 입력에서 출력까지 거치는 기본 단위 회로의 개수가 회로의 복잡함을 나타낼 수 있을 것이다. 입력으로 사용되는 숫자의 크기가 n이라고 했을 때 덧셈 회로는 log n에 비례하는 단계를 거친다. 정확한 값은 알 수 없으나 log n에 상수비례하는 값을 표현하기 위해 O(log n)와 같이 표기한다. 이렇게 입력에서 출력까지의 회로 단계수, 즉 복잡도가 O(log n)인 회로들을 NC1 이라고 부른다. 이는 컴퓨터 알고리듬에서 P, NP 라고 종류를 나눈 것과 유사하다.

나눗셈, 곱셈, 거듭제곱과 같은 계산 회로의 복잡도는 O(log n)보다 크다고 알려져 있었으나 스티븐 쿡은 O(log n)의 복잡도를 가지는 회로를 고안하여 제안했다.​8​

  1. ​*​
    출처: https://en.wikipedia.org/wiki/Stephen_Cook, CC BY-SA 3.0
  2. ​†​
    팀 호튼즈는 캐나다의 대중적인 패스트푸드 체인이다. 커피와 도넛이 유명하다.
  3. ​‡​
    출처: https://en.wikipedia.org/wiki/Stephen_Cook, CC BY-SA 4.0
  4. ​§​
    유리스 하트마니스는 1993년에 튜링상을 수상했다.
  5. ​¶​
    리처드 “딕” 매닝 카프는 1985년에 튜링상을 수상했다.
  6. ​#​
    로버트 플로이드는 1978년에 튜링상을 수상했다.
  7. ​**​
    토니 호어는 1980년대 튜링상을 수상했다.

참고문헌

  1. 1.
    Cook Stephen A. An overview of computational complexity. ACM Turing Award Lectures.:1982. doi:10.1145/1283920.1283938
  2. 2.
    Stephen Cook: 1982 ACM Turing Award Recipient, Interviewed by Bruce Kapron. ACM; 2016:15.
  3. 3.
    Cook Stephen A. The complexity of theorem-proving procedures. Proceedings of the third annual ACM symposium on Theory of computing  – STOC ’71. Published online 1971. doi:10.1145/800157.805047
  4. 4.
    Stephen A Cook. A.M. Turing Award Laureate. Accessed December 6, 2022. https://amturing.acm.org/award_winners/cook_n991950.cfm
  5. 5.
    코플랜드 B잭. 앨런 튜링: 컴퓨터와 정보 시대의 개척자. 지식함지; 2014.
  6. 6.
    P vs NP Problem. Clay Mathematics Institute. Accessed December 7, 2022. https://www.claymath.org/millennium-problems/p-vs-np-problem
  7. 7.
    Cook Stephen A. Soundness and Completeness of an Axiom System for Program Verification. SIAM J Comput. Published online February 1978:70-90. doi:10.1137/0207005
  8. 8.
    Beame Paul W, Cook Stephen A, Hoover H James. Log Depth Circuits for Division and Related Problems. SIAM J Comput. Published online November 1986:994-1003. doi:10.1137/0215070

(c) 이재범, 2023
이 콘텐츠는 대한민국 저작권법의 보호를 받습니다. 작성된 모든 내용의 권리는 저자에게 있으며, 저자의 동의 없는 사용은 금합니다. 본 콘텐츠의 일부 혹은 전체 내용을 무단으로 전재/복제/배포하거나 2차적 저작물로 재편집하는 경우, 법적 책임을 지게 됩니다.

1 2 3 4