コンピューターサイエンスの歴史で最も影響力のある論文7本

アラン・チューリングの計算機械に始まり、コンピューターサイエンスの歴史を大きく変えて後世に強い影響を与えた科学論文について、ソフトウェアエンジニアのマテウス・リマ氏が代表的な7本を紹介しました。

The 7 Most Influential Papers in Computer Science History – Terrible Software
https://terriblesoftware.org/2025/01/22/the-7-most-influential-papers-in-computer-science-history/

リマ氏は「あくまで主観的なリスト」と前置きしつつ、7本を紹介しています。

◆1：計算可能数とその決定問題への応用／アラン・チューリング(1936)
1930年代、「プログラム可能な機械」なぞ絵に描いた餅だと考えられていた時代に、コンピューターの基礎を築いたのがアラン・チューリングです。この論文でチューリングは仮想的な「チューリング・マシン」をスケッチし、何かが計算可能であれば、原理的には機械がそれを扱えることを証明しました。

今日、あらゆるプログラミング言語、あらゆるコードが、チューリングのルールに従っています。最先端の量子コンピューティングについて話すときでさえチューリングが説明した境界を参照していることから、リマ氏は「1930年代半ばに発表された1つの論文が以下に大きな力を持っているかを示しています」と紹介しました。

On Computable Numbers, with an Application to the Entscheidungsproblem
(PDFファイル)https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

◆2：コミュニケーションの数学理論／クロード・シャノン(1948)
チューリングが機械にできることとできないことを教えてくれた後、実際に情報を動かすにはどうすればいいのかを示した論文です。シャノンは「情報理論」を発明し、ビット、エントロピーなど測定可能な情報について厳密な方法で語れるようにしました。

リマ氏は「あなたがテキストメールを送ったり、映像をストリーミングしたり、FaceTimeでお母さんに電話したりするたびに、シャノンのアイデアが使われていることになります」と紹介しました。

A Mathematical Theory of Communication
(PDFファイル)https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf

◆3：大規模共有データバンクのためのデータのリレーショナル・モデル／エドガー・F・コッド(1970)
計算も通信もできるコンピューターが最終的にはデータの山に埋もれてしまうことを予見し、データの保存とクエリを可能にする「リレーショナル・モデル」について書かれた論文です。データベースの「テーブル」やSQLなど、現代の幅広い技術に影響を与えました。

A Relational Model of Data for Large Shared Data Banks
(PDFファイル)https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf

◆4：定理証明手続きの複雑さ／スティーブン・A・クック(1971年)
一つの命題論理式が与えられたとき、それに含まれる変数の値を偽(False)あるいは真(True)にうまく定めることによって全体の値を真にできるか、という問題「充足可能性問題」がNP完全であることを示した論文です。リマ氏は「充足可能性問題を魔法のように素早く解けば、他の一見不可能な問題の束を即座に解いたことになる」と解説しています。

The Complexity of Theorem-Proving Procedures
(PDFファイル)https://www.inf.unibz.it/~calvanese/teaching/14-15-tc/material/cook-1971-NP-completeness-of-SAT.pdf

◆5：パケットネットワーク相互通信のためのプロトコル／ヴィントン・G・サーフ、ロバート・E・カーン(1974)
1970年代初頭、ARPANETをはじめ、世界中に構築され始めていたネットワークはそれぞれ異なるハードウェアとソフトウェアのプロトコルに従って動作していたため、相互に通信することは不可能でした。この問題はサーフとカーンがトランスミッション・コントロール・プロトコル(TCP)というネットワーク横断プロトコルを発明したことで解決され、コンピュータネットワークの国際的なネットワーク、すなわち「インターネット」の構築が進められることになりました。

A Protocol for Packet Network Intercommunication
(PDFファイル)https://www.cs.princeton.edu/courses/archive/fall06/cos561/papers/cerf74.pdf

◆6：情報管理:提案／ティム・バーナーズ＝リー(1989)
ティム・バーナーズ＝リーはハイパーリンク、URL、HTTPを完備したグローバル・ハイパーテキスト・システムを提案した人物で、この論文をもってWorld Wide Webが発明されたと見なされています。

Information Management: A Proposal
(PDFファイル)https://cds.cern.ch/record/369245/files/dd-89-001.pdf

◆7：大規模ハイパーテキスト・ウェブ検索エンジンの解剖／セルゲイ・ブリン、ラリー・ペイジ(1998)
セルゲイ・ブリン、ラリー・ペイジは、インターネット上にあふれる情報をまとめて表示しやすくする「検索エンジン」の1つを構築した人物。キーワードに対する関連性の高い検索結果が飛躍的に増加し、ウェブを検索可能にした功績があります。両者は、Googleの創立メンバーです。

The Anatomy of a Large-Scale Hypertextual Web Search Engine
(PDFファイル)https://snap.stanford.edu/class/cs224w-readings/Brin98Anatomy.pdf

リマ氏は「私たちは新しいものにまみれています。度肝を抜くようなAIのブレークスルー、量子コンピューター、JavaScriptフレームワークなど、どれもとてもエキサイティングですが、重要なのは基礎です。基礎がなければ、土台を十分に理解しないまま新しいおもちゃを積み上げるだけです。ここで紹介した論文は、データ構造、アルゴリズム、まさにウェブといった我々の核となる概念がどこから来たのかを思い出させてくれるものです」と述べました。