算法与理论计算机2017arxiv.org
超计算：超越图灵机的计算
Hypercomputation: Computing more than the Turing machine (2002)
进阶 · 约 60 分钟读完前置知识：可计算性理论、图灵机、停机问题
导读
这篇 2002 年的论文讨论“超计算”（hypercomputation）：是否存在或可定义超越图灵机可计算性范围的计算模型，以及相关主张意味着什么。结合 HN 评论看，讨论核心不是具体算法，而是这类模型是否有物理基础、是否依赖无限时间/内存，以及能否绕过停机问题。
HN 关注点：超计算是否只是数学游戏：它缺乏物理可实现性，相关主张常被批评为“允许不可计算输入就能得到不可计算输出”。
HN 评论精选
这几条评论里：质疑 3 补充 1
质疑超计算缺乏物理基础，相关主张本质上只是允许不可计算输入。
也许我有偏见，但我通常对超计算相关帖子持怀疑态度。Davis 在《The Myth of Hypercomputation》中指出：在“超计算”旗号下，人们声称某些计算模式可行、超出图灵可计算性；但所有目前接受的物理理论都无法处理无限精度的实数。批判地看，这些主张无非是在说：如果允许不可计算输入，就能得到不可计算输出。图灵论文的原意是图灵机实际可实现，很多人也真做出了能计算东西的图灵机；而超计算没有物理基础，用它建模现实几乎无用。
z1mm32m4n查看英文原文
Maybe I'm biased, but I generally view posts about hypercomputation with skepticism. From The Myth of Hypercomputation[1]: > Under the banner of "hypercomputation" various claims are being made for the feasibility of modes of computation that go beyond what is permitted by Turing computability. In this article it will be show n that such claims fly in the face of the inability of all currently accepted physical theories to deal with infinite precision real numbers. When the claims are viewed critically, it is seen that they amount to little more than the obvious comment that if non-computable inputs are permitted, then non-computable outputs are attainable. The original idea in Turing's thesis was that the Turning Machine was something that could actually be implemented, and indeed you can find many examples of people's side projects where such machines can be made and can actually compute things. On the other hand, hypercomputation has no physical basis. So what's the point of using it to model anything real? It's next to useless. [1]: http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf
补充回忆一个声称有限时间完成无限工作的超计算模型，并表达失望。
多年前 A.K. Dewdney 在 Scientific American 的计算休闲专栏讨论过比图灵机/lambda 演算/递归函数更强的计算模型。他提出的模型能在（？）线性时间解决 NP-Hard 问题：把输入传给两个子处理器，子处理器要么解决，要么再各传给两个子子处理器；每个子处理器规模是父处理器一半，且因线延迟耗时与其规模成正比（？）。总之它能在有界时间内完成无界量的工作。此后我就不再关注 Dewdney 了。
mcguire查看英文原文
Way back, years ago, A.K. Dewdney published one of his computing recreations columns in Scientific American where he discussed models of computation stronger than Turing machines/lambda calculus/recursive functions/etc., etc. His contribution was a model that solved a NP-Hard (?) problem in linear time: it passed the input to two sub-processors, which either solved the problem or passed it to two sub-sub-processors each. Since each sub-processor was half the size of its parent and required time proportional to its size due to wire delay (?). Anyway, the bottom line was that it did an unbounded amount of work in a bounded amount of time. I stopped paying attention to Dewdney after that.
质疑讽刺超计算依赖无法实现的无限资源。
简而言之：如果有无限时间或无限内存，你能完成很多工作。至于如何实现其中之一，就留给读者作练习。
idlewords查看英文原文
In a nutshell: you can get a lot of work done if you have infinite time or infinite memory. The implementation of either is left as an exercise for the reader.
质疑用停机问题构造自指矛盾，论证超计算不可能。
我猜想超计算不可能，理由很简单：如果你能解决停机问题，你就能构造一个“活生生的矛盾”——一台当且仅当它不停机时才停机的机器（证明见 Sipser）。那不只是悖论描述，而是实际矛盾。如果矛盾可能（我们通常认为不可能），现实会比我们观察到的更离奇。
trishankkarthik查看英文原文
I conjecture that hypercomputation is impossible for the following simple reason. If you could solve the Halting Problem [1], then you could build a "living" contradiction, where a machine halts if and only if it does not halt. (See proof in [2]). It won't be a mere description of a paradox, it would be an actual one. If contradictions are possible (something we implicitly believe to be impossible), then Reality is far stranger than we ever suspected or observed. [1] https://en.wikipedia.org/wiki/Halting_problem [2] https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
历次讨论
- 2017Hacker News 讨论帖143 分 · 70 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选