算法与计算机科学beza1e1.tuxen.de
意外图灵完备的事物合集（2013）
A collection of things that are Turing-complete by accident (2013)
2013 — 2022，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这个页面收集了一批「意外地」图灵完备的系统——它们原本并非为计算而设计，却因为规则足够丰富，能够表达任意计算，比如 C 预处理器、BGP 路由配置、Super Mario World、万智牌等。作者对每个条目都给出了简要说明和原始出处，展示图灵完备性常常在不经意间冒出来。
为什么经久不衰：它把「计算」这一抽象概念拉进游戏、协议和日常工具里，每次重读都提醒我们计算能力可以藏在最意想不到的地方，而且清单随新研究不断增补。
HN 评论精选
补充 Dwarf Fortress 这一遗漏项，并指出「无限纸带」在实际游戏里普遍无法满足。
清单里漏掉了《矮人堡垒》(Dwarf Fortress)。如果你想一边抵御哥布林进攻和僵尸、一边试着造一台计算机，那它再合适不过了。严格来说它不算图灵完备，因为它的「纸带」不是无限的，不过其他号称图灵完备的游戏也有同样的问题。
toomanybeersies查看英文原文
Missing from the list is Dwarf Fortress: http://dwarffortresswiki.org/index.php/DF2014:Computing Great when you want to try and create a computer while trying to fend off goblin attacks and zombies. Technically, it's not Turing Complete, as the "tape" is not unlimited, but other Turing Complete games have the same issue.
BGP 路由配置可以模拟逻辑电路，是最令人着迷的条目之一。
那篇用 BGP 搭建逻辑门的论文非常有意思，感谢分享。论文揭示了 BGP 配置与逻辑电路之间的根本映射：用带有基本 BGP 配置的路由器就能模拟逻辑门、时钟和触发器，再把它们互联起来模拟任意逻辑电路。
carlsborg查看英文原文
The paper where they build logic gates with BGP is fascinating. Thanks for posting this. "In this paper, we answer computational complexity questions by unveiling a fundamental mapping between BGP configurations and logic circuits. Namely, we describe simple networks containing routers with elementary BGP configurations that simulate logic gates, clocks, and flip-flops, and we show how to interconnect them to simulate arbitrary logic circuits."
补充 x86 mov 指令图灵完备的极端案例，性能代价极其夸张。
x86 的 mov 指令也是图灵完备的！有人只用 mov 指令就跑起了 Doom，当然慢得惊人——每 7 小时才渲染一帧。
kbumsik查看英文原文
Also x86 mov instruction is Turing complete! [1] There is a guy who run Doom with only mov instructions, but it is of course incredibly slow, one frame every 7 hours :) [2] [1]: https://news.ycombinator.com/item?id=9751312 [2]: https://news.ycombinator.com/item?id=16218872
万智牌的不可判定性来自强制走法，与图灵机的本质一致，并不神秘。
关于万智牌是图灵完备的，有个引述很有意思：「我们的结果很不寻常，因为构造中双方的所有走法都是被强制的。这说明即便一局游戏双方都无需做任何非平凡决策，判断谁会赢仍然不可判定。」起初我觉得这对一款游戏来说很震撼，但这其实与图灵机直接可比：每一步都是机械、被迫且容易推导的，整体行为却通常不可判定。
FartyMcFarter查看英文原文
On Magic The Gathering being Turing-complete, this is an interesting quote: > Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. At first I thought this was pretty mind-blowing for a game, but actually this is directly comparable with a Turing machine; each step is forced, mechanical and very easy to derive, and yet, the overall behaviour is generally undecidable.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选