《量子雜志》每周都會解釋推動現代研究的最重要思想之一。本周，計算機科學專欄作家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

科普薦書

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數學科普不迷路！