計算は普遍的な基本概念か——Tim Roughgardenが問う、コンピュータの限界
Computation as a Universal and Fundamental Concept
Tim Roughgarden教授が、コンピュータの能力と限界を探る講義を公開。1936年のAlan Turingの理論から始まり、停止問題やNP完全性、P vs NP問題まで、計算の本質を解説する。アルゴリズムの力と限界を、地図アプリのDijkstra法や巡回セールスマン問題などの具体例で示し、暗号、AI、量子計算への影響も考察。前提知識不要で、講義はYouTubeでも視聴可能。
Turingの論文は、彼の名を冠した理論上の機械を導入し、驚くべきことを証明した。どんなに時間や計算能力を費やしても、決して解けない問題が存在するのだ。