컴퓨터 과학 역사에서 가장 영향력 있는 논문들

 (terriblesoftware.org)
6P by GN⁺ | ★ favorite | 댓글 1개
  • 1936년부터 1998년까지의 컴퓨터 과학 논문 7편은 계산 가능성, 정보 이론, 데이터베이스, 복잡도, 인터넷, 웹, 검색이라는 현대 컴퓨팅의 핵심 층위를 형성함
  • Alan Turing의 1936년 논문은 Turing Machine으로 기계가 원리적으로 계산할 수 있는 것과 없는 것을 구분하며 현대 계산 모델의 출발점이 됨
  • Claude Shannon, Edgar F. Codd, Stephen A. Cook은 각각 정보 측정과 오류 정정, 관계형 데이터 모델, NP-completeness와 SAT를 통해 통신·데이터·문제 난이도의 공통 언어를 만듦
  • Vinton G. Cerf와 Robert E. Kahn, Tim Berners-Lee, Sergey Brin과 Larry Page의 논문은 TCP/IP, World Wide Web, PageRank로 네트워크 연결·문서 연결·웹 검색의 구조를 잡음
  • 보너스 목록의 Lisp, 구조적 프로그래밍, 논리 시계, 소프트웨어 복잡성, Transformer까지 보면 새 도구보다 기초 개념을 이해하는 일이 더 오래 남는 경쟁력이 됨

선정 기준과 전체 흐름

  • 목록은 절대적인 순위가 아니라, 오늘날 세계에 미친 영향력을 기준으로 고른 주관적 선택임
  • 7편은 날짜순으로 정렬되어 계산, 통신, 데이터 저장, 계산 난이도, 네트워킹, 웹, 검색으로 이어지는 흐름을 보여줌
  • 새로운 언어, AI 발전, 양자 도약, JavaScript 프레임워크가 계속 등장해도 현대 컴퓨팅의 바탕에는 이 논문들이 만든 개념이 남아 있음

1. “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936)

2. “A Mathematical Theory of Communication” (1948)

3. “A Relational Model of Data for Large Shared Data Banks” (1970)

  • Edgar F. Codd는 대규모 데이터를 저장하고 질의하기 위한 관계형 모델을 제안함
  • 핵심 아이디어는 데이터를 테이블에 저장하고 논리 연산으로 조작하는 방식임
  • 이 설계는 SQL과 관계형 데이터베이스 계열로 이어져 은행, 소매 웹사이트, 엔터프라이즈 시스템을 뒷받침함
  • NoSQL 시대에도 테이블, 스키마, 일관성 같은 데이터 조직 개념은 Codd의 모델과 연결되어 있음
  • 더 읽기:

4. “The Complexity of Theorem-Proving Procedures” (1971)

5. “A Protocol for Packet Network Intercommunication” (1974)

  • Vinton G. Cerf와 Robert E. Kahn의 논문은 고립된 네트워크들을 연결하는 TCP의 기반을 제시함
  • 서로 다른 네트워크가 대화할 수 있는 보편적인 언어가 생겼고, 데이터는 작은 패킷으로 나뉘어 여러 경로를 지난 뒤 반대편에서 재조립됨
  • 이 유연성 덕분에 하나의 거대한 단일 네트워크 없이도 전 지구적 연결이 가능해짐
  • 웹 탐색, 이메일 전송, 은행 웹사이트 로그인 같은 활동은 TCP/IP가 bit를 안정적으로 이동시키는 것에 기대고 있음
  • 일부 실시간 애플리케이션은 UDP를 쓰지만, Cerf와 Kahn이 제시한 IP 기반 네트워킹의 핵심 아이디어는 기기들을 하나의 글로벌 네트워크 아래 묶음
  • 더 읽기:

6. “Information Management: A Proposal” (1989)

7. “The Anatomy of a Large-Scale Hypertextual Web Search Engine” (1998)

  • Sergey Brin과 Larry Page는 링크와 페이지가 폭증한 웹을 다루기 위해 링크 분석 기반 접근법을 만들었고, 이것이 Google 검색 엔진으로 발전함
  • 핵심 아이디어인 PageRank는 링크를 단순한 키워드 계산 요소가 아니라 신뢰의 투표로 봄
  • 이 방식은 관련성 높은 검색 결과를 크게 개선해 웹을 검색 가능한 공간으로 만듦
  • Google에 질문을 입력해 즉시 답을 얻는 경험은 PageRank와 이후의 많은 혁신 위에서 동작함
  • PageRank는 온라인 정보 탐색 방식을 재정의했고 광고, 분석, 머신러닝 등 데이터 기반 기술의 새 시대를 여는 계기가 됨
  • 더 읽기:

본문에 거의 포함될 뻔한 5편

  • “Recursive Functions of Symbolic Expressions and Their Computation by Machine” (1960) – John McCarthy
    • Lisp와 함수형 프로그래밍 스타일을 도입했으며, 이 스타일은 현대 언어와 프레임워크에도 남아 있음
  • “Go To Statement Considered Harmful” (1968) – Edsger Dijkstra
    • goto가 지저분하고 비구조적인 코드를 만든다고 비판하며 구조적 프로그래밍 혁명을 촉발함
  • “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) – Leslie Lamport
    • 분산 시스템에서는 실제 시계를 완벽히 동기화할 수 없기 때문에 논리 시계가 필요함
  • “No Silver Bullet—Essence and Accident in Software Engineering” (1986) – Fred Brooks
    • 소프트웨어 개발의 본질적 복잡성을 해결할 단 하나의 마법 같은 방법은 없다고 봄
  • “Attention Is All You Need” (2017) – Vaswani et al.
    • GPT와 여러 유명 AI 모델 뒤에 있는 Transformer 아키텍처를 제시함

기초 개념이 남긴 영향

  • 오늘날에는 새 언어, AI 혁신, 양자 도약, 매주 등장하는 JavaScript 프레임워크가 계속 쏟아짐
  • 데이터 구조, 알고리듬, 웹 같은 핵심 개념이 어디서 왔는지 이해하지 못하면 새로운 도구만 계속 쌓는 상황이 됨
  • 이 7편과 보너스 논문들은 현대 컴퓨팅의 핵심 토대가 된 아이디어들을 되짚게 함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Communicating Sequential Processes(Hoare), The Next 700 Programming Languages(Landin), As We May Think(Bush), Can Programming Be Liberated from the von Neumann Style(Backus)도 넣을 만함
    그리고 이 강의도 좋아 보임: https://canvas.harvard.edu/courses/34992/assignments/syllabu...
    “이 강의는 1930년대부터 현재까지 모든 컴퓨터 과학자가 읽었어야 할 논문들을 다룬다. 컴퓨터 과학 고급 학생들이 분야 전체를 조망하도록 돕는 종합 경험이며, 단순한 개관이 아니라 그 창조 과정을 다시 체험하게 하는 방식이다. 이미 어느 정도 배경지식이 있는 학생들에게 컴퓨터 과학의 전체 진화를 빠른 속도로 재생해 보여줌으로써, 분야에 대한 통합된 관점을 만들려는 목적이다”

    • 강의를 보려면 Harvard 계정이 필요한 것 같음

  • 이 목록은 좀 이상한 조합처럼 느껴짐. 컴퓨터 과학, 즉 계산 이론에 영향을 준 논문을 고르는 건지, 기술에 영향을 준 논문을 고르는 건지, 아니면 그냥 “컴퓨터 관련 모든 것”을 컴퓨터 과학이라고 부르는 건지 애매함
    Turing 논문은 컴퓨터 과학의 기반이지만, 그 논문이 없었다고 기술이 다르게 발전했을지는 의문임. 대부분의 소프트웨어 엔지니어는 읽어본 적도 없음. 반대로 IP 표준은 기술적 초석이지만 과학적 내용은 거의 없고, 네트워크 주변 일을 하려면 알아야 하는 비교적 단순한 프로토콜 명세에 가까움

    • PageRank 논문이 Turing과 Shannon의 계산 가능성·정보 이론 기초 연구와 짧은 목록 안에 나란히 있는 건 어딘가 맞지 않아 보임
      “On Computable Numbers, with an Application to the Entscheidungsproblem”은 이제 거의 90년이 됐지만 지금도 당시만큼 참이고 유효함. PageRank가 1998년만큼 지금도 관련성이 있는지, 더 나아가 50년 뒤에도 그럴지는 잘 모르겠음

  • 좋은 논문 목록임. 목록의 7편 중 5편을 읽었고, 아직 안 읽은 건 Cerf와 Kahn의 논문, Berners-Lee의 논문임
    Turing의 계산 가능성 논문은 특히 따라가기 어려웠는데, 온갖 대상을 고딕체 대문자로 이름 붙였고 그 글자들이 다 비슷해 보였기 때문임. 보조 자료를 봐야 논문을 읽어낼 수 있었고, 지금이라면 Charles Petzold의 해설서 https://www.amazon.com/Annotated-Turing-Through-Historic-Com...와 함께 읽는 걸 추천함
    Cook의 NP-완전성 논문도 역시 어려웠고, Turing 논문처럼 보조 자료가 필요했음. 지금이라면 Cook의 증명을 따라가는 계산 복잡도 입문서를 먼저 읽는 편을 추천함
    Shannon의 논문은 명확하고 아름답게 쓰인 예술 작품 같지만, 가볍게 읽을 만한 글은 전혀 아님
    Brin과 Page의 논문, Codd의 논문은 기억상 크게 어렵지 않았지만, Brin과 Page의 작업을 이해하려면 어느 정도 선형대수 지식이 필요함

    • Brin과 Page 논문에서 선형대수가 어디에 필요한지 모르겠음. “고유벡터”라는 말은 한 번 나오지만 부수적인 언급임
      “단순 반복 알고리즘”은 선형이든 아니든 임의의 축소 사상의 고정점을 찾는 방식임. 그것이 고유벡터이기도 하다는 사실은 오히려 방해에 가깝고, 잘 아는 사람이라면 가우스 소거법을 쓰지는 않을 것임
    • .tex 원본 파일을 구할 수 있다면 GPT에게 변수명을 더 읽기 좋게, 한 글자보다 긴 이름으로 바꿔 달라고 하면 도움이 됨

  • Shannon의 A Mathematical Theory of Communication이 컴퓨터 과학에 남긴 가장 근본적인 기여라고 생각한다면, 그가 10년 전 쓴 석사 논문을 아직 못 본 것임
    https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
    그는 회로의 스위칭 요소, 즉 트랜지스터로 불 논리를 정의할 수 있음을 제시했음
    물론 정보 이론 전체의 기반을 세운 업적의 중요성을 낮추려는 뜻은 아님

  • “무언가 계산 가능하다면 원칙적으로 기계가 처리할 수 있음을 보이며 가상의 ‘Turing Machine’을 그려냈다”는 설명은 Turing이 증명한 내용이 아님
    그 논문에서 그가 증명한 것은 Turing Machine으로 풀 수 없는 문제가 존재한다는 것이고, 따라서 아마 어떤 기계로도 풀 수 없다는 것임. 제목에 있는 Entscheidungsproblem, 즉 결정 문제가 바로 그것임
    원문이 가리키는 건 이른바 Church-Turing Thesis인데, 말 그대로 명제에 가까움. 실제로 증명할 수는 없지만, 거의 100년 동안 Turing Machine보다 더 강력한 계산 체계를 찾지 못했다는 점에서 매우 강하게 믿을 이유가 있음

    • 지난 100년 동안 인공지능이 어디에 있는지에 대한 생각은 오히려 완전히 반대 방향으로 갔음
      알려진 모든 진리를 담은 기계를 만드는 대신, 현대의 기계 기반 인공지능 탐색은 대체로 인간의 논평을 뒤져 정리된 feuilleton 기계를 만드는 쪽에 가까워졌고, Leibniz식 공리적 접근과는 다름
    • “Turing Machine보다 더 강력한 계산 체계를 아무도 찾지 못했다”는 말은 틀렸다고 봄. Turing Machine은 비결정성을 수행할 수 없지만, actor 모델은 가능함

  • 좋은 작업임. 비슷한 걸 개인적으로 하고 있었어서 몇 편을 더 추천해 봄
    RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978)
    PageRank: The PageRank Citation Ranking: Bringing Order to the Web (1999)
    MapReduce: MapReduce: simplified data processing on large clusters (2008)
    Bitcoin: Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
    역전파: Learning representations by back-propagating errors (1986)
    Hoare 논리: An Axiomatic Basis for Computer Programming (1969)

  • Dennis Ritchie의 악명 높은 Evolution of Unix time-sharing systems는 어디 갔나?
    https://www.bell-labs.com/usr/dmr/www/cacm.pdf

  • 다들 자기 추천을 보태고 있으니 나도 하나 추가하자면, Cook이 NP-완전성을 처음 소개하긴 했지만, Karp가 3SAT로 다항 시간 환원이 가능한 21개 문제를 제시한 논문도 Cook의 이론에 대한 더 넓은 관심을 촉발한 거대한 초석이었음
    https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...

  • Diffie와 Hellman의 New Directions in Cryptography(1976)는 빠진 건가?

  • 논문은 아니지만 Marc Andreessen의 Why Software Is Eating the World와 Amazon의 1997년 첫 주주서한은 특별히 언급할 만함
    “모든 산업의 기업은 소프트웨어 혁명이 오고 있다고 가정해야 한다. 오늘날 이미 소프트웨어 기반인 산업도 여기에 포함된다”
    https://a16z.com/why-software-is-eating-the-world/
    “하지만 지금은 인터넷의 Day 1이고, 우리가 잘 실행한다면 Amazon.com에게도 Day 1이다”
    https://www.aboutamazon.com/news/company-news/amazons-origin...

답변달기