算法与计算机科学gwern.net
你的电脑里有多少台计算机？
How Many Computers Are in Your Computer?
2015 — 2020，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 Gwern 长文《Turing-complete》中的一节，讨论一台现代电脑里其实还藏着多少台“电脑”：CPU 内的管理/功耗微控制器、BMC、网卡、硬盘、充电器等都可能包含独立处理器和固件。它把“图灵完全”的视角扩展到这些隐蔽的计算单元，提醒我们日常设备是层层嵌套的计算系统。
为什么经久不衰：它用层层嵌套的嵌入式处理器揭示现代硬件的隐蔽复杂度，多年后仍然贴切，也让人重新思考“一台电脑”到底意味着什么。
HN 评论精选
现代 CPU、网卡、存储和 BMC 里都有多个独立嵌入式处理器，实际数量远超直觉。
CPU 通常还包含多个独立的小 CPU 来控制节能、睿频等。现代 Intel CPU 有多个 486 级 CPU：一个管这些，一个跑 ME，还有一个供厂商使用且能访问 SMM（这跟 ME 一样可怕甚至更甚）。OpenPOWER 挺有意思，因为你能看到商业相关固件实现长什么样。很多网卡也完全基于多个通用 MIPS 核，比如 Broadcom 和 Mellanox。最常见的 LSI/Broadcom SAS HBA 是 PowerPC SoC。SATA/SAS 硬盘用多个 ARM Cortex M 系列 MCU 处理总线接口、驱动器几何结构，闪存盘还用于 FTL。BMC（IPMI）也是一台自给自足的 ARM 电脑。
kev009查看英文原文
The cpu also has typically multiple independent CPUs to control things like power saving and turbo boost. Modern intel cpus have multiple 486-class CPUs, one for this, one for the ME, and one that vendors can use that has SMM access (which is as scary or more so than the ME). OpenPOWER is pretty neat because you can actually see what commercially relevant implementations of these firmwares look like https://github.com/open-power/occ A lot of NICs are also completely based on multiple general purpose MIPS cores like Broadcom and Mellanox. The most common SAS HBA from LSI/Broadcom was a PowerPC SoC. And SATA/SAS drives are running multiple ARM Cortex M series MCUs for the bus interface, drive geometry, and FTL in the case of flash. The BMC (IPMI) is also a self sufficient ARM computer.
实际嵌入式电脑数量可能比原文估计还多一个数量级，外设和固件里到处都是 MCU。
一台“电脑”里的电脑可能比 Gwern 估计的还要多一个数量级。想想：电源管理芯片（有几十个）每个都含可编程 MCU；电池当然也各含一个或多个 MCU；时钟；DMA/USB 控制器等“胶水”MCU（USB 控制器固件曾从端口侧被利用，而且不可升级）；监控器；RGB LED（！）；SD 卡有好几个（见 Bunnie 的工作）；以太网、WiFi 和蓝牙控制器各含几个小电脑，通常还有几个大的。它们有的用固化 ROM 代码，有的可通过 flash 编程修改，有的为省钱在驱动加载时才写入固件。
ianhowson查看英文原文
There are probably another order of magnitude more computers in a 'computer' than Gwern estimates. Consider: - Power management chips (of which there are dozens) each containing programmable MCUs - Batteries, of course, contain one or more MCUs each - Clocks - 'Glue' MCUs for things like DMA controllers and USB controllers. (USB controller firmware has been exploited from the port side, and it's not upgradeable) - Supervisors - RGB LEDs (!) - SD cards have several (see Bunnie's work) - Ethernet, WiFi and Bluetooth controllers contain several small and usually a few large computers each Some of these have fully-baked ROM code, some are programmed and modifiable through flash, and some have firmware written at driver load time to save money.
连充电器里的 MSP430 都是图灵完全，可被用于功耗侧信道攻击。
再补一个：MacBook 充电砖里有一颗 MSP430，“大致和初代 Macintosh 里的处理器一样强”。它肯定是图灵完全的；你可能无法大量访问机器其余部分，但它可以作为发起功耗侧信道攻击的立足点（是的，你只能得到整体功耗，但这不构成障碍）。
moyix查看英文原文
To add a one more: the Macbook charging bricks have an MSP430 in them [1], "roughly as powerful as the processor inside the original Macintosh". It's definitely Turing complete; you may not get tons of access to the rest of the machine, but it might serve as a vantage point from which to launch power-based side channel attacks [2] (yes, you only get the overall power draw from this but that's no barrier [3]). [1] http://www.righto.com/2015/11/macbook-charger-teardown-surprising.html [2] https://en.wikipedia.org/wiki/Power_analysis [3] https://m.tau.ac.il/~tromer/handsoff/ "Our attacks use novel side channels and are based on the observation that the "ground" electric potential in many computers fluctuates in a computation-dependent way."
SQL 标准曾刻意避免图灵完全，但 CTE 和窗口函数等扩展最终让它变成图灵完全。
我最喜欢的例子是 SQL。ANSI-92 标准故意让 SQL 不是图灵完全，以便优化。但人们不断加东西，比如 CTE 和窗口函数，现在它是了。
btilly查看英文原文
My favorite example is SQL. The ANSI-92 standard deliberately made SQL not Turing Complete so that it could be optimized. But people kept adding things to it, like CTE and windowing, and now it is. See http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf for proof.
历次讨论
同类还值得读
位运算技巧集
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编辑精选