TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Accidentally Turing-Complete

25 点作者 bschne18 天前

5 条评论

256_18 天前
Logic in Doom is particularly interesting to me. Apparently you can fit ~64k logic gates in a map (using the method described). From [1]:<p>&quot;As the DOOM engine was not designed to be an interpreter, there are some constraints on our programs written against it. The biggest one is how large our programs can be. Since each gate uses at least one tag, we can use this as a metric to derive an upper-bound on the size of a program. As the DOOM engine uses 16-bit tags, this means we can have, at most, 65535 gates. This is not a particularly large number. We may be able to implement a very small CPU but this limit will be hit pretty quickly I believe.&quot;<p>The z80 had ~8,500 transistors. The 8086 had ~29,000 (checking Wikipedia). You could get far fewer if you use a 1-bit microarchitecture, I&#x27;m sure. I think there was a DEC (PDP?) computer that used that trick to have a really low transistor count, but I don&#x27;t remember what it was called.<p>The real problem is RAM; for this you may as well cheat and modify Doom&#x27;s code to add a RAM chip, and I&#x2F;O while you&#x27;re at it.<p>You could create a CPU in Doom implementing an architecture for which a C compiler exists, capable of compiling Doom, and run it in the CPU in Doom. For &quot;reasonable&quot; speed you&#x27;d have to do more than one simulation step per frame render (in the host Doom). If you ran it for long enough maybe you could get a full frame of Doom in Doom.<p>[1]: <a href="https:&#x2F;&#x2F;calabi-yau.space&#x2F;blog&#x2F;doom.html" rel="nofollow">https:&#x2F;&#x2F;calabi-yau.space&#x2F;blog&#x2F;doom.html</a>
评论 #43815559 未加载
karmakaze18 天前
My favorite one is Conway&#x27;s Game of Life. It&#x27;s perhaps the least surprising one, but it&#x27;s also the most visually appealing. Really like this video that leads up to making the Game of Life in itself[0]. It&#x27;s something you can show a non-technical person and they can get a sense of how crazy it is that something so simple can do anything.<p>[0] <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=Kk2MH9O4pXY" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=Kk2MH9O4pXY</a>
a_cardboard_box18 天前
Rule 110 is only Turing-Complete if you have an infinitely large array of cells, and are able to initialize it with an infinite repeating pattern. If I&#x27;m not mistaken, HTML+CSS can only do a fixed-sized array.<p>With a Turing-Complete language, if a program runs out of memory on one machine, you can run the same code on a bigger machine without modifying it, and it can use the additional memory. With fixed-length rule 110, you need to modify the code if you want to use more memory.
评论 #43813948 未加载
panstromek18 天前
Nice list. Some of those are arguably not accidental, TypeScript type system seems kinda obvious to be turing complete when it tries to describe dynamically typed langauage.
WalterGR18 天前
x86 MOV instruction: “The mov-only DOOM [game] renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience.”