算法与理论计算机2009arxiv.org编辑精选
物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
专业 · 约 180 分钟读完前置知识：范畴论基础、量子力学基础、类型论/数理逻辑
导读
这篇论文用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态射。它强调这些领域共享的数学语言，而不是做具体计算。
HN 关注点：John Baez 的科普写作、范畴论跨领域类比，以及它和类型论/Haskell 实现之间的关联。
后来怎么样
它系统整理的对称幺半闭、紧致闭与 dagger 范畴对应，成为范畴量子力学和应用范畴论的常用参考框架，影响了后续量子协议、自然语言语义等方向的范畴化工作。
HN 评论精选
这几条评论里：补充 3
补充推荐 Baez 的主页作为高质量的科普与数学资源。
John Baez 是一位极出色的作者。他的主页满是精彩的插图和阐述性内容（物理、数学、气候科学等）：http://math.ucr.edu/home/baez/
FredrikMeyer查看英文原文
John Baez is a fantastic writer. His home page is full of wonderful illustrations and expository stuff (physics, mathematics, climate science, ...) http://math.ucr.edu/home/baez/
补充指出该论文的思想有一个 Haskell 相关实现 Subhask，并说明它大幅改动了 Functor/Monad 体系。
还有一个基于这项工作、面向 GHC 的代码库叫 Subhask。它技术上仍是 Haskell，但替换了太多 Functor/Monad 层级，实际上已经像另一门语言。https://github.com/mikeizbicki/subhask
tbenst查看英文原文
There's also a code base for GHC based on this work called Subhask. It's technically Haskell but replaces so much of the functor/monad hierarchy that it's effectively a different language. https://github.com/mikeizbicki/subhask
补充读者追问类型论与范畴论的区别和联系，反映讨论延伸到类型论。
类型论和范畴论有什么区别？它们之间有什么关系？
zengid查看英文原文
What's the difference between type theory and category theory? How are they related?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2009Hacker News 讨论帖44 分 · 4 评
- 2014Hacker News 讨论帖99 分 · 9 评
- 2016Hacker News 讨论帖101 分 · 11 评
- 2017Hacker News 讨论帖146 分 · 31 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选近线性时间内的最大流与最小费用流
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
给出了最大流与最小费用流的近线性时间精确算法，是理论计算机科学的重要突破。
算法与理论计算机2022 · 230 分 · 40 评 · 引用 8专业 · 约 120 分钟编辑精选