コンピュータサイエンス史で最も影響力のある論文たち
(terriblesoftware.org)- 1936年から1998年までのコンピュータサイエンス論文7本が、計算可能性、情報理論、データベース、計算複雑性、インターネット、Web、検索という現代コンピューティングの中核的な層を形作った
- 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によって、ネットワーク接続・文書接続・Web検索の構造を定めた
- ボーナス一覧にあるLisp、構造化プログラミング、論理時計、ソフトウェア複雑性、Transformerまで見渡すと、新しいツールよりも基礎概念を理解することのほうが、より長く競争力として残ることが分かる
選定基準と全体の流れ
- この一覧は絶対的な順位ではなく、今日の世界に与えた影響力を基準に選んだ主観的なセレクションである
- 7本は年代順に並べられており、計算、通信、データ保存、計算の難しさ、ネットワーキング、Web、検索へと続く流れを示している
- 新しい言語、AIの進化、量子分野の飛躍、JavaScriptフレームワークが次々に登場しても、現代コンピューティングの土台にはこれらの論文が築いた概念が残っている
1. “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936)
- Alan Turingは1930年代に、仮想的なTuring Machineを通じて、コンピュータが理論的に何をできるのかという基盤を築いた
- 中核モデルは、テープ、読み書きヘッド、有限の状態集合で構成される
- このモデルは、機械的な意味で解ける問題と、解けない問題が何かを定義した
- すべてのプログラミング言語とコードはTuringが定義した規則の中で動作しており、量子コンピューティングを語るときでさえ、Turingが示した境界が参照される
- さらに読む:
2. “A Mathematical Theory of Communication” (1948)
- Claude Shannonは情報を厳密に扱うために情報理論を築き、bit、entropy、noisy channelといった概念を体系化した
- 抽象的だった「情報」は測定可能な対象となり、データ圧縮と誤り訂正符号の基盤が整えられた
- 宇宙に信号を送る場合からNetflixのストリーミングまで、データを効率よくパッケージ化し、誤りから保護するためにこの考え方が使われている
- 文字送信、動画ストリーミング、FaceTime通話のような日常的な通信も、Shannonの概念の上に成り立っている
- さらに読む:
3. “A Relational Model of Data for Large Shared Data Banks” (1970)
- Edgar F. Coddは大規模データを保存し、問い合わせるための関係モデルを提案した
- 核心のアイデアは、データをテーブルに保存し、論理演算で操作する方式である
- この設計はSQLと関係データベース群へとつながり、銀行、小売Webサイト、エンタープライズシステムを支えている
- NoSQL時代になっても、テーブル、スキーマ、一貫性といったデータ構成の概念はCoddのモデルと結び付いている
- さらに読む:
4. “The Complexity of Theorem-Proving Procedures” (1971)
- Stephen A. Cookの論文は、一部の計算問題が非常に難しいことを扱い、NP-completenessの概念を導入した
- CookはBoolean satisfiability problem、すなわちSATがNP-completeであることを示した
- SATを高速に解ければ、他の多くの難しい問題もあわせて解けるという形で、問題の難しさを語る共通言語が生まれた
- 「NP-hard」という表現や、経路最適化がCPUに重い負荷をかけるような状況は、この論文の影響につながっている
- この概念は、アルゴリズム、暗号学、効率的解法や近似解法の探索に大きな影響を与えた
- さらに読む:
5. “A Protocol for Packet Network Intercommunication” (1974)
- Vinton G. CerfとRobert E. Kahnの論文は、孤立したネットワーク同士をつなぐTCPの基盤を提示した
- 異なるネットワークが対話できる普遍的な言語が生まれ、データは小さなパケットに分割され、複数の経路を通った後に受信側で再構成される
- この柔軟性によって、単一の巨大ネットワークがなくても地球規模の接続が可能になった
- Web閲覧、メール送信、銀行Webサイトへのログインのような活動は、TCP/IPがbitを安定して移動させることに依存している
- 一部のリアルタイムアプリケーションはUDPを使うが、CerfとKahnが示したIPベースのネットワーキングという中核アイデアは、機器を1つのグローバルネットワークの下に束ねている
- さらに読む:
6. “Information Management: A Proposal” (1989)
- Tim Berners-Leeは、機械同士が容易に通信できるようになった後、人々がより使いやすく利用できるWorld Wide Webの方向性を提案した
- 核心のアイデアは、ハイパーリンク、URL、HTTPを備えたグローバルなハイパーテキストシステムである
- 世界中の文書はもはや孤立せず相互につながり、インターネットは科学者だけでなく一般ユーザーも探索できる形になった
- ソーシャルメディア、オンラインショッピング、深夜3時に読むブログ記事のようなWeb体験の種は、この提案から生まれた
- さらに読む:
7. “The Anatomy of a Large-Scale Hypertextual Web Search Engine” (1998)
- Sergey BrinとLarry Pageは、リンクとページが爆発的に増えたWebを扱うためにリンク解析ベースのアプローチを作り、これがGoogle検索エンジンへと発展した
- 中核アイデアであるPageRankは、リンクを単なるキーワード計算要素ではなく、信頼の投票として捉えた
- この方式は関連性の高い検索結果を大幅に改善し、Webを検索可能な空間に変えた
- 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
- ソフトウェア開発の本質的な複雑さを解決する、たった1つの魔法のような方法は存在しないと論じた
- “Attention Is All You Need” (2017) – Vaswani et al.
- GPTや多くの著名なAIモデルの背後にあるTransformerアーキテクチャを提示した
基礎概念が残した影響
- 今日では、新しい言語、AIの革新、量子分野の飛躍、毎週現れるJavaScriptフレームワークが絶えず押し寄せている
- データ構造、アルゴリズム、Webといった中核概念がどこから来たのかを理解しなければ、新しいツールを積み上げ続けるだけの状態になってしまう
- これら7本とボーナス論文群は、現代コンピューティングの中核的な土台となったアイデアを改めて振り返らせてくれる
1件のコメント
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年代から現在まで、すべてのコンピュータ科学者が読むべきだった論文を扱う。コンピュータサイエンスの上級学生が分野全体を見渡せるようにする総合的な経験であり、単なる概観ではなく、その創造のプロセスを追体験させる形を取る。すでにある程度の背景知識を持つ学生に、コンピュータサイエンスの進化全体を高速に再生して見せることで、この分野への統合的な視点を作ることを目的としている」
このリストは少し奇妙な組み合わせに感じる。コンピュータサイエンス、つまり計算理論に影響を与えた論文を選んでいるのか、技術に影響を与えた論文を選んでいるのか、それとも単に「コンピュータ関連のあらゆるもの」をコンピュータサイエンスと呼んでいるのかが曖昧
Turing の論文はコンピュータサイエンスの基盤だが、その論文がなかったとして技術が違った形で発展したかどうかは疑問。ほとんどのソフトウェアエンジニアは読んだことすらない。逆に IP 標準は技術的な礎石ではあるが、科学的な内容はほとんどなく、ネットワーク周辺の仕事をするなら知っておくべき比較的単純なプロトコル仕様に近い
“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 の仕事を理解するにはある程度の線形代数の知識が必要
「単純な反復アルゴリズム」は、線形かどうかに関係なく任意の縮小写像の不動点を見つける方法。それが固有ベクトルでもあるという事実はむしろ邪魔に近く、よく分かっている人ならガウス消去法は使わないだろう
.texの元ファイルを入手できるなら、GPT に変数名をもっと読みやすく、1文字より長い名前に変えてもらうと役に立つ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 より強力な計算体系が見つかっていないことから、非常に強く信じる理由がある
既知のすべての真理を含む機械を作る代わりに、現代の機械ベースの人工知能探索はおおむね人間の論評を漁って整理された feuilleton マシンを作る方向に近づいており、Leibniz 的な公理的アプローチとは異なる
いい仕事。似たようなことを個人的にやっていたので、いくつか追加で推薦してみる
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)
ホーア論理: 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
https://web.archive.org/web/20070926212100/http://www.almade...
みんな自分のおすすめを足しているので、私も一つ追加すると、Cookが NP完全性 を初めて紹介したのは確かだが、3SATから多項式時間還元できる21個の問題を提示したKarpの論文も、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...