小乐数学科普：2024年我在计算机科学方面学到了什么——《量子杂志》每周数学随笔|密码学|小乐|数学科普|科学|计算机|量子杂志

《量子杂志》每周都会解释推动现代研究的最重要思想之一。本周，计算机科学专栏作家Ben Brubaker（本·布鲁贝克）剖析了计算机科学的真正含义，并讨论了近一年报道中的一些亮点。

作者：Ben Brubaker 2024-12-2

译者：zzllrr小乐（数学科普公众号）2024-12-3

图源：Quanta Magazine

当我告诉人们我写关于计算机科学的文章时，他们常常不确定我的意思。我写的内容包括软件？网络安全？还是最新的硅谷小工具？实际上，我很少涉及这些内容。先驱研究员 Edsger Dijkstra（艾兹赫尔·韦伯·迪杰斯特拉，1930 - 2002）的一句精辟名言帮助我解释了这一点：“计算机科学与计算机的关系并不比天文学与望远镜的关系更密切。”

作为一名记者，我主要关注理论计算机科学，这是该领域的一个分支，比现代数字计算机的发明早了几十年。它源于艾伦·图灵和其他研究人员对数学过程进行数学形式化的努力，该领域的部分内容仍然具有类似的自指性，我发现这同样令人困惑和高兴。

真正的计算机可以推动理论计算机科学的发展，就像望远镜推动天文学的发展一样。一旦研究人员开始使用计算机解决问题，他们就会意识到需要精确的数学语言来描述他们正在开发的程序，即算法。这引发了关于算法行为和基本限制的新问题——这些问题被证明非常微妙，以至于半个世纪后研究人员仍在试图解答它们。

如果你抛开那些让你眼花缭乱的复杂数学符号和缩写，你会发现这些问题通常相当简单。是什么让一些问题比其他问题更难？随机性意味着什么？物理定律与信息有什么关系？我们如何研究那些我们不了解其内部工作原理的算法？

2022年，当我开始以记者的身份报道计算机科学时，我对这个主题几乎一无所知。在我过去作为实验物理学家的人生中，我的编程经验主要涉及在文档不全的代码中寻找错误。这不是最能激发智力的工作，我不确定我能发现该领域的理论方面更有吸引力。但我很快就明白，这些担忧是没有根据的。两年过去了，每次写故事时，我仍然在学习令人着迷的新事物。以下是 2024 年我最喜欢的一些故事。

最新动态和值得关注的内容

自1970年代以来，计算机科学家一直使用一种称为计算复杂性理论的统一数学框架来研究不同问题的难度。在1980和1990年代，量子物理学的新见解挑战了关于某些问题有多难的传统观点，但它们并没有改变哪些问题在原则上是可解的。现在，理论密码学的一系列最新成果提供了诱人的证据 https://www.quantamagazine.org/cryptographers-discover-a-new-foundation-for-quantum-secrecy-20240603/ ，表明量子物理学的一些问题可能完全超出了复杂性理论的框架。量子复杂性的前景可能比研究人员想象的要奇怪得多。

这些关于量子复杂性理论的发现最近才出现，这也许并不奇怪——毕竟，这些都是相当令人头疼的课题。但研究人员也在更实际的问题上取得了令人震惊的新发现，比如寻找通过道路网络的最短路线。1956年，广为人知的 Dijkstra 开发了一种解决此问题的简单算法。到1980年代，研究人员已经证明他的算法是最佳算法，在一个特定的理论意义上：在最坏的情况下，它比任何其他方法都能更快地找到这些最短路径。但最近，一组研究人员发现，对 Dijkstra 算法进行微小的调整，使其在许多其他情况下也无可匹敌。 https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/ 这很好地说明了研究人员仍然可以从已经研究了几十年的经典算法中学到新的东西。

不过，我最喜欢的 2024 年计算机科学突破不是关于快速算法，而是关于被亲切地称为“忙碌海狸”（busy beavers）的极其缓慢的算法。研究人员研究这些计算生物，以了解看似简单的计算机程序可以完成的最复杂的事情。到 1974 年，研究人员发现了一系列四只忙碌的海狸，每只都比前一只更忙碌。今年，一群在网上合作的海狸猎人最终确定了该系列中的第五只——BB(5)=47176870https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ 。这是一个精彩的故事，用一位读者的话来说，“角色阵容似乎直接来自迈克尔·刘易斯的书”。如果你今年读我写的一个故事，那就读它吧。

网络上的新闻

如果你还想了解更多，我鼓励你查看合作发生的Discord 聊天服务器。很少有如此详细的数学发现过程记录。题外话的讨论也很有趣——它们让我陷入了困境，关于在桌面卡牌游戏《万智牌：聚会》（Magic: The Gathering，MTG）中会出现多么荒谬的大数字。 https://www.quantamagazine.org/wp-content/uploads/2024/11/Massive-Damage-Challenge-Old.pdf

3月份，我参加了由加州伯克利西蒙斯计算理论研究所主办的关于计算机科学写作的小组讨论 https://simons.berkeley.edu/news/communicating-algorithmic-science-public 。我谈到了作为一名记者报道理论计算机科学的挑战，以及我让抽象主题变得通俗易懂的方法。（西蒙斯研究所得到了西蒙斯基金会的资助，该基金会还支持量子杂志成为一家独立编辑的出版物。）

去年网上流传着一则轶事，关于一名研究人员向警方报告一辆自行车被盗，这说明了计算机科学不仅仅是研究计算机：

“后来，我在剑桥计算机科学家中找到一个聊天室帖子，其中一人也被告知，除非他能确定盗窃时刻，否则没有人会查看录像。他说他试图向警方解释排序算法--毕竟，他是一名计算机科学家。

你不需要看整个过程，他说。你使用二分查找。你快进到一半看看自行车是否在那里，如果在那里，就放大到四分之三处。但如果在中间位置没有找到自行车你就快进到四分之一处。这非常快。事实上，他指出，如果闭路电视录像可以追溯到人类黎明时期，那么找到盗窃时刻可能只需要一个小时。这个论证没有得到很好的接受。” https://x.com/AlecStapp/status/1728953538301345889

参考资料

https://mailchi.mp/quantamagazine.org/why-colliding-particles-reveal-reality-4865746

https://www.quantamagazine.org/cryptographers-discover-a-new-foundation-for-quantum-secrecy-20240603/

https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/

https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/

https://www.quantamagazine.org/wp-content/uploads/2024/11/Massive-Damage-Challenge-Old.pdf

https://simons.berkeley.edu/news/communicating-algorithmic-science-public

https://x.com/AlecStapp/status/1728953538301345889

https://mp.weixin.qq.com/s/gE13ZWQXFIeRKEoMJTOw2w

科普荐书

·开放 · 友好 · 多元 · 普适 · 守拙·