算法与理论计算机2017andrew.cmu.edu
论 MS PowerPoint 的图灵完备性
On the Turing Completeness of MS PowerPoint
入门 · 约 30 分钟读完前置知识：图灵机基础、计算理论初步
导读
这篇论文证明 MS PowerPoint 在图灵等价意义上是图灵完备的：作者利用 PowerPoint 的动画与交互机制（不借助宏或插件）在其内实现了一个可运行的图灵机。论文配有演示视频，展示该机制实际运行的效果。
HN 关注点：HN 读者对'看似不可能的日常软件其实是完备计算系统'这类趣味性计算机科学结果很感兴趣，且演示视频幽默、直观。
HN 评论精选
这几条评论里：补充 3 亲历 1
补充配套视频比论文本身更有趣直观
推荐观看论文配套视频，很有笑点：https://www.youtube.com/watch?v=uNjxe8ShM-8
raoulj查看英文原文
The video accompanying this paper (recommend watching for a good laugh): https://www.youtube.com/watch?v=uNjxe8ShM-8
补充调侃该工作获 Ig Nobel 奖，并戏称 PowerPoint 之强与 Sun 之亡
这项工作获得了搞笑诺贝尔计算机科学奖。看来 Scott McNealy 当年封杀 PowerPoint 的决定，反而催生了能力更弱的系统，从而导致 Sun 的衰亡。
watersb查看英文原文
Ig Nobel Prize in Computer Science It is now clear that Scott McNealy's banishment of PowerPoint required the creation of much less-capable systems, and thus to the demise of Sun.
补充递归套娃式展望
下一步：在 PowerPoint 里模拟 PowerPoint。
tonmoy查看英文原文
Next step, emulate powerpoint within powerpoint
亲历吐槽重复提交现象，提出'同群体问题'，并推荐视频形式
这已经是不到两个月内第二十次被提交到 HN 了。这类网站需要重大创新来应对内容重复与读者轮换的问题——读者群体不断更替，导致'已看过'的内容反复出现，我称之为'同群体问题'。另外 Algolia 显示此帖发布于 19 小时前而 HN 显示 3 小时前，很奇怪。我还是认为视频是体验这项工作的更好方式，因为演讲者幽默且能看到实际运行；我还在本季编程语言课程第一课上放了这段视频。
saurik查看英文原文
This is literally the twentieth (!!) time in less than two months that this talk/paper has been submitted to Hacker News. The entire concept of this kind of website (Hacker News / reddit / etc.) really needs some major innovation to deal with this variability of response to content combined with repetition of material over time due to the rotation of readers (which eventually leads people to move to new communities of people with a different seed base of "stuff already seen"; a problem I call "the cohort problem" and have given talks about at times). (There is also something weird going on where Algolia claims this specific post appeared 19 hours ago while Hacker News itself claims it appeared only 3 hours ago. What's up with that?) As mentioned in another comment, I will argue the video is a much better way to experience this, due to a combination of the humor of the presenter and being able to watch it actually function. (After seeing it on Hacker News when it was posted six or seven weeks ago, I showed this video to the first day of a class I am teaching this quarter on the nature of programming languages.) https://news.ycombinator.com/item?id=14016364
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2017Hacker News 讨论帖160 分 · 16 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选