计算作为普遍且基本的概念

# 计算作为普遍且基本的概念 — Ergo 来源：https://ergo.org/courses/computation-as-a-universal-and-fundamental-concept Tim Roughgarden 从一个看似简单的问题开始：是否存在计算机无法完成的事情？为了回答这个问题，他带我们回到 1936 年，当时距实际计算机出现还有十年，艾伦·图灵在解决一个晦涩的数学问题过程中，无意间奠定了计算机科学的基础。图灵的论文提出了以他命名的理论机器，并证明了一个令人震惊的事实：有些问题是任何算法都无法解决的，无论投入多少时间或算力。停机问题（判断一个程序最终是否会停止运行）永远超出了任何计算机的能力范围。 从这个基础出发，Roughgarden 转向一个更微妙的问题：在计算机能够解决的问题中，哪些可以快速解决？他介绍了算法捷径——巧妙的技巧，让程序无需检查每一种可能的解决方案。你的手机地图应用基于 Dijkstra 算法来找到最短路线，而不必检查所有可行路径。Karatsuba 乘法方法优于我们学过的传统方法。这些捷径几乎像魔法一样，同时引发了一个自然的希望：也许每个问题都存在这样的捷径。 但这个希望撞上了旅行商问题（TSP）。尽管和最短路径问题看起来几乎相同，TSP 却抵制了所有寻找快速算法的尝试。Roughgarden 解释了这个谜题如何引出了 NP 完全性理论，这是计算机科学中最令人惊讶的发现之一。成千上万个看似无关的问题（调度、解谜、网络优化）原来都是同一核心挑战的不同伪装。如果有人找到其中任何一个问题的快速算法，所有问题都会变得容易；如果其中任何一个确实是难解的，那么所有问题也都是难解的。 这引出了 P 与 NP 问题，这是计算机科学中最重要的开放问题，也是数学中未解的重大难题之一。Roughgarden 通过 Hilbert、Gödel 和 von Neumann 等人物追溯其历史，展示了两个独立的研究传统——一个关注算法能实现什么，另一个关注算法的局限性——如何汇聚到这个单一问题上。课程最后探讨了答案可能对密码学、人工智能、量子计算以及我们对计算本身的理解意味着什么。不需要任何计算机科学或数学背景。 你可以观看下面的讲座，浏览章节索引（https://ergo.org/courses/computation-as-a-universal-and-fundamental-concept/chapters/），或在 YouTube 上观看（https://www.youtube.com/playlist?list=PL1GBzfniaE7xovcAP1LbbTi7UXsqEoCyl）。 Tim Roughgarden ## Tim Roughgarden Tim Roughgarden 是高等研究院数学学院教授。他此前在哥伦比亚大学计算机科学系任教七年，在斯坦福大学任教十五年。他的主要研究兴趣在于计算机科学与经济学之间的联系，以及算法的设计、分析与局限性。 他是《算法博弈论二十讲》（https://www.cambridge.org/us/universitypress/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/twenty-lectures-algorithmic-game-theory?format=PB&__cf_chl_f_tk=pCO4OHaEokRB4kHEE0DsdPsylXqpwfF0QSGoKdU6FwY-1782743575-1.0.1.1-Hf5JDHRy641D22d24DgodFARDbJZik9ivZ5vlJld6Ys）、《超越最坏情况算法分析》（https://www.cambridge.org/core/books/beyond-the-worstcase-analysis-of-algorithms/8A8128BBF7FC2857471E9CA52E69AC21）以及《算法详解》系列（https://timroughgarden.org/books.html）的作者，并发表了大量研究论文。他的工作获得了理论计算机科学领域的多项重要奖项，包括 ACM 格雷斯·默里·霍珀奖和哥德尔奖。