Tim Roughgarden从图灵1936年的理论出发，指出计算机存在无法解决的问题（如停机问题），并探讨了算法捷径的局限性。尽管许多问题可通过巧妙算法快速求解，但旅行商问题等难题至今未找到高效解法，揭示了计算能力的根本边界。

蒂姆·拉夫加登从一个看似简单的问题出发：计算机是否无所不能？为了回答这个问题，他带我们回溯到1936年，当时艾伦·图灵在真正的计算机诞生前十年，通过解决一个晦涩的数学问题，意外奠定了计算机科学的基础。图灵的论文提出了以他命名的理论机器，并证明了一个惊人的事实：存在一些算法永远无法解决的问题，无论投入多少时间或计算能力。停机问题——即判断一个程序是否会最终停止运行——就是计算机永远无法触及的难题。

基于这一基础，拉夫加登转向一个更微妙的问题：在计算机能解决的问题中，哪些能快速解决？他介绍了算法捷径——那些让程序避免检查所有可能解的巧妙技巧。你的手机地图应用基于迪杰斯特拉算法，无需检查每条路径就能找到最短路线；卡拉楚巴乘法方法则超越了我们在学校学到的传统算法。这些捷径看似神奇，让人不禁期待：或许每个问题都存在这样的捷径。

然而，这种希望被旅行商问题击碎。尽管与最短路径问题看似相似，旅行商问题却一直未能找到快速算法。拉夫加登解释了这一难题如何引出了NP完全性理论——计算机科学中最令人惊讶的发现之一。数千个看似无关的问题（如调度、解谜、网络优化）实际上都是同一核心挑战的不同伪装。如果任何人找到了其中任何一个问题的快速算法，所有问题都会变得简单；如果任何一个问题真正困难，那么所有问题都困难。

这引出了P与NP问题——计算机科学中最重要的未解之谜，也是数学领域最伟大的未解难题之一。拉夫加登通过希尔伯特、哥德尔和冯·诺依曼等人物追溯其历史，展示了两个独立的研究传统——一个关注算法能实现什么，另一个关注其局限性——如何汇聚到这一问题上。课程最后探讨了答案可能对密码学、人工智能、量子计算以及我们对计算本身的理解意味着什么。无需计算机科学或数学背景即可学习。

根据评论内容，主要围绕“计算是否具有普遍性和基础性”展开讨论，观点分歧明显。以下是总结：

观点一：计算是普遍且基础的概念 - 支持者认为计算概念远超最初想象，甚至与宇宙运行等同（sgt101: "Computation has turned out to be a far more general concept... many computer scientists now seem to equate computation with the functioning of the universe"）。 - 部分评论强调计算在哲学和科学中的核心地位（Diogenesian: "Computation is a metaphysically universal and fundamental concept"）。

观点二：计算并非宇宙基础，而是人类形式系统 - 批评者指出计算模型（如图灵机、λ演算）是人类创造的形式主义，不能等同于现实（jdw64: "Turing machines, lambda calculus... they're all human-made formalisms"）。 - 认为将计算视为宇宙法则是一种范畴错误（lo_zamoyski: "These rest on category errors... intentionality rules out computation as an extra-mental phenomenon"）。 - 历史类比显示，人类常将新技术（如时钟、蒸汽机）误认为宇宙本质（kaashif: "every time a new technology is invented... people start to think it explains everything"）。

观点三：计算的局限性 - 现实物理过程存在不可判定性（sgt101: "real, physical processes which are undecidable... we cannot know if a lattice of atoms has a spectral gap"）。 - 停机问题在涉及外部输入时无法解决（jojogeo: "The second you touch any external peripherals... you're effectively asking... 'Will they pick up the phone?'"）。

观点四：计算与智能的关系 - 智能不依赖计算，仅生物智能在某些情境下依赖（summarybot: "intelligence itself does not rely on computation, only its biological counterweight seems to"）。 - 计算是观察者视角的产物（vatsachak: "Computation is in the eye of the beholder"）。

平衡性总结：评论呈现明显对立——一方认为计算是宇宙基础，另一方强调其人类形式系统的局限性。中间立场承认计算的普遍性，但反对将其等同于现实本质。多数评论对“计算基础论”持批判态度，认为这是范畴错误或历史类比的重演。