算法与理论计算机2021arxiv.org
为什么哲学家应关注计算复杂性（2011）
Why philosophers should care about computational complexity (2011)
入门 · 约 90 分钟读完前置知识：计算复杂性基础、P vs NP 问题、哲学基本概念
导读
这是 Scott Aaronson 的一篇论文（2011），主张哲学界应当认真对待计算复杂性理论：P vs NP、不可计算性、复杂性类等概念能把「图灵测试与机器能否思考」「他心问题」「自由意志」「模拟假说」「数学知识」等经典哲学问题重新表述得更精确。文章的核心论点是：忽略复杂性（只谈可计算性）会让许多哲学争论停留在含糊层面，而复杂性给出了区分「原则上可能」与「实际可行」的量化工具。
HN 关注点：复杂性理论能否真正为意识、AI 与模拟论证等哲学难题提供新工具，讨论焦点也包括「中文房间」这类经典思想实验与计算时间的关系。
HN 评论精选
哲学界早有 SEP 专条讨论计算复杂性与可计算性，这篇论文本身也已被收录引用。
哲学家确实关心[1][2]。* 顺带一提，原帖（OP）本身就被这两个条目引用。
guerrilla查看英文原文
They do [1][2]*. 1. https://plato.stanford.edu/entries/computational-complexity/ 2. https://plato.stanford.edu/entries/computability/ * Note that the OP is even cited there.
用中文房间引出「计算时间」维度：足够慢的符号操作能否等同于智能或意识。
最近了解了中文房间实验后，它一直在我脑中萦绕。强烈推荐去把这个论证弄明白，因为某种意义上它把「复杂性」和「计算所需时间」联系了起来。如果一屋子机器人按简单指令运转十亿年，才能表现得像一个会读中文的 AI，那么这些机器人算不算一种集体智能？这能否扩展到意识层面？
mensetmanusman查看英文原文
The Chinese Room has been on my mind lately after recently learning about it: https://en.m.wikipedia.org/wiki/Chinese_room Highly recommend trying to grasp the argument, because in a sense it connects complexity to ‘time to compute’. If it takes a room of robots following simple instructions a billion years to act as an AI that reads Chinese, are those robots a collective intelligence? Can it be scaled up to consciousness?
以绕口令式的玩笑提问调侃「计算所有可计算数」这一概念的可行性。
问题：「如果一台计算机能计算所有可计算数，那它能计算多少个可计算数？」土拨鼠对此很好奇。
photochemsyn查看英文原文
Question: "How many computable numbers could a computer compute if a computer could compute all computable numbers?" Woodchucks are curious about this.
这是 HN 上被反复讨论的经典文章，附历次讨论存档。
以往讨论帖：（列出 2018、2016、2015、2011 年共五个 HN 帖子链接）
dang查看英文原文
Past threads: Why Philosophers Should Care About Computational Complexity (2011) [pdf] - https://news.ycombinator.com/item?id=17573142 - July 2018 (22 comments) Why Philosophers Should Care About Computational Complexity (2011) [pdf] - https://news.ycombinator.com/item?id=11913825 - June 2016 (54 comments) Why Philosophers Should Care About Computational Complexity [pdf] - https://news.ycombinator.com/item?id=9061744 - Feb 2015 (43 comments) Why Philosophers Should Care About Computational Complexity - https://news.ycombinator.com/item?id=2897277 - Aug 2011 (10 comments) Why Philosophers Should Care About Computational Complexity - https://news.ycombinator.com/item?id=2861825 - Aug 2011 (36 comments)
历次讨论
- 2021Hacker News 讨论帖171 分 · 143 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
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 分钟编辑精选