算法与理论计算机2017arxiv.org
一位计算机科学家眼中的生命、宇宙与一切 (1999)
A Computer Scientist’s View of Life, the Universe, and Everything (1999)
入门 · 约 60 分钟读完前置知识：计算理论基础、算法复杂度、哲学/宇宙学常识
导读
这是 Schmidhuber 1999 年的论文，从计算机科学视角探讨宇宙的本质：假设我们的宇宙是某个“大程序员”在一台大计算机上运行的所有可能计算宇宙之一。核心论点是计算所有可能宇宙的程序很短（简单算法枚举一切），而单独计算某一个特定宇宙反而代价高昂，因为几乎所有宇宙都是不可压缩的——“多即是少”。
HN 关注点：HN 读者对 Schmidhuber 的“计算宇宙”假说与模拟宇宙论、算法信息论的联系感兴趣，讨论其哲学含义与论证是否成立。
HN 评论精选
这几条评论里：质疑 2 补充 2
质疑调侃论文思想早被莱布尼茨提出，引用缺失
Schmidhuber 忘了引用莱布尼茨。本文的结果不过是“形而上学效率原则”的平凡推论，更不用说莱布尼茨早在 1710 年就发现了其最一般形式的“前定和谐”，它不仅涵盖物理宇宙的构造，还涵盖道德。参见斯坦福哲学百科相关条目。
gabrielgoh查看英文原文
Schmidhuber has forgotten to cite Leibniz. The results in this document are nothing more than a trivial corollary of the principle of metaphysical efficiency, not to mention pre-established harmony, which Leibniz has discovered the most general forms of in 1710, which encompasses not only the construction of the physical universe, but also morality. See https://plato.stanford.edu/entries/leibniz-evil/.
质疑引用精彩段落，但对“多即是少”的论证提出疑问
“大程序员的若干宇宙中会出现另一个大程序员，编程另一台大计算机运行所有可能的宇宙。显然存在无穷链条的大程序员。如果我们宇宙有足够存储、时间和无故障计算，你也可以成为其中之一。”很喜欢这句。但我不懂文章这个要点：“只计算某一个特定宇宙的演化（比如带一种特定噪声）而不计算其他宇宙，往往非常昂贵，因为几乎所有个体宇宙都是不可压缩的。”似乎是说计算所有宇宙的程序短，而计算单个宇宙的程序长，但前者的运行时间不是更长吗？有人能解释吗？
jatsign查看英文原文
"Several of the Great Programmer’s universes will feature another Great Programmer who programs another Big Computer to run all possible universes. Obviously, there are infinite chains of Great Programmers. If our own universe allowed for enough storage, enough time, and fault-free computing, then you could be one of them." Loved that line. I do not understand this main point of the article. Perhaps someone can explain? "On the other hand, computing just one particular universe’s evolution (with, say, one particular instance of noise), without computing the others, tends to be very expensive, because almost all individual universes are incompressible, as has been shown above. More is less!" It seems the point is that the program to compute all universes is short, while the program to compute one particular universe is long. But surely runtime is greater in the former?
补充推荐相关阅读资料
顺着这个思路，我强烈推荐 Scott Aaronson 的《为什么哲学家应该关心计算复杂性》。
heydenberk查看英文原文
In this vein, I strongly recommend Scott Aaronson's Why Philosophers Should Care About Computational Complexity http://www.scottaaronson.com/papers/philos.pdf
补充补充作者后续相关论文
我们刚被 Schmidhuber 化了！还有他 2009 年的论文《哥德尔式的终极认知》。
visarga查看英文原文
We've just been Schmidhubered! There's also this paper from 2009 : > "Ultimate Cognition a la Godel" http://www.brainmaster.com/software/pubs/math/Godel%20machine.pdf
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 评论区提到的论文
历次讨论
- 2017Hacker News 讨论帖202 分 · 73 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选