frontpage.
newsnewestaskshowjobs

Open Source @Github

fp.

Open in hackernews

Accidentally Turing-Complete

https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html
25•bschne•1y ago

Comments

panstromek•1y ago
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.
WalterGR•1y ago
x86 MOV instruction: “The mov-only DOOM [game] renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience.”
a_cardboard_box•1y ago
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'm not mistaken, HTML+CSS can only do a fixed-sized array.

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.

256_•1y ago
This is addressed in the second paragraph of TFA:

"Stuff which is somehow limited (stack overflows, arbitrary configuration, etc) is still considered Turing complete, since all "physical" Turing machines are resource limited."

In my opinion, worrying about infinite memory, in regards to Turing completeness, makes the task of implementing computation much less interesting.

Also, I'm pretty sure CSS only does one generation (or a finite number of them) before stopping anyway.

256_•1y ago
Logic in Doom is particularly interesting to me. Apparently you can fit ~64k logic gates in a map (using the method described). From [1]:

"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."

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'm sure. I think there was a DEC (PDP?) computer that used that trick to have a really low transistor count, but I don't remember what it was called.

The real problem is RAM; for this you may as well cheat and modify Doom's code to add a RAM chip, and I/O while you're at it.

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 "reasonable" speed you'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.

[1]: https://calabi-yau.space/blog/doom.html

karmakaze•1y ago
Doom running in TypeScript static type checker[0].

> half trillion lines of types totaling 177 terabytes ran through the type checker around the clock for 12 days to get the first frame

[0] https://news.ycombinator.com/item?id=43184291

karmakaze•1y ago
My favorite one is Conway's Game of Life. It's perhaps the least surprising one, but it's also the most visually appealing. Really like this video that leads up to making the Game of Life in itself[0]. It'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.

[0] https://www.youtube.com/watch?v=Kk2MH9O4pXY

Three small failures combined to take down Microsoft 365

https://arstechnica.com/gadgets/2026/11/microsoft-details-how-three-problems-combined-for-a-globa...
1•ishqdehlvi•55s ago•0 comments

Archaeologists uncover sections of medieval church [video]ters

https://www.reuters.com/video/watch/idRW891617112026RP1/
1•thunderbong•2m ago•0 comments

Big tech engineers need big egos

https://www.seangoedecke.com/big-tech-needs-big-egos/
1•peter_d_sherman•4m ago•0 comments

How to compress text to 1 bit per character

https://www.youtube.com/watch?v=qbsb9DpdZ6s
1•saikiran91•4m ago•0 comments

Sched_ext: A sketch of the scx_lavd scheduler (Part 3)

https://blogs.igalia.com/changwoo/sched-ext-a-sketch-of-the-scx-lavd-scheduler-part-3/
1•multics69•5m ago•0 comments

Hey Anthropic, make a dating app

https://wilsoniumite.com/2026/11/18/hey-anthropic-make-a-dating-app/
1•Wilsoniumite•6m ago•0 comments

My Dog Ate Jelly Beans – What to Do Now (Check This First) – PetToxCheck

https://pettoxcheck.com/dogs/my-dog-ate-jelly-beans/
1•lena_suzuki•7m ago•0 comments

Show HN: Sip pacer that helps you drink slower

https://pourdecision.app/blog/sip-pacing-method
1•OzBuilds•9m ago•0 comments

10k sounds, 64 mixer slots: how much work can a game audio engine skip?

https://ssenthilnathan3.github.io/blog/sonic/
1•nathaah3•12m ago•0 comments

How to Interview Your Interviewers

https://blog.alinelerner.com/how-to-interview-your-interviewers/
1•kurinikku•13m ago•0 comments

What Context Does a Coding Agent Actually Need

https://arxiv.org/abs/2607.09691
1•freshtake•15m ago•0 comments

Owning the Truth: Undecidability, unsound kernels, and the forging of proof

https://phrack.org/issues/73/owning-the-truth-undecidability-unsound-kernels-and-the-forging-of-p...
1•matt_d•16m ago•0 comments

A Transformer-Derived Iterative Preconditioner

https://arxiv.org/abs/2611.22941
1•E-Reverance•16m ago•0 comments

Show HN: New chess variant – liminal chess

https://levmiseri.com/liminalchess/
1•levmiseri•23m ago•0 comments

I Loved Big Walk. Then I Found Out How They Made It

https://siroccomask.substack.com/p/i-loved-big-walk-then-i-found-out
1•kicksent•23m ago•0 comments

An agent skill for hill-climbing the speed of a local LLM server

https://github.com/sybil-solutions/inference-optimisation-skil
1•ayanb9440•25m ago•0 comments

Mosquitoes are Ladakh's latest tourists

https://ruralindiaonline.org/article/mosquitoes-are-ladakh-s-latest-tourists
2•akbarnama•28m ago•0 comments

'Human' Is the Cambridge Dictionary's Word of 2026

https://www.nytimes.com/2026/11/17/style/human-cambridge-word-year-2026.html
2•1659447091•32m ago•0 comments

Huang Blocker

https://mergy.org/huang-blocker/
2•mergy•37m ago•1 comments

18th-Century Sculpture Has a Delicate Net Carved Out of a Single Marble(2025)

https://mymodernmet.com/francesco-queirolo-the-release-from-deception/
2•iamanatom•39m ago•2 comments

Italian Sculptor Created a Marble Masterpiece(2019)

https://2.boredpanda.com/marble-sculpture-net-francesco-queirolo-release-from-deception/
2•iamanatom•41m ago•0 comments

High-Speed Signaling Drill-Down (2020)

https://semiengineering.com/high-speed-signaling-drill-down/
2•peter_d_sherman•42m ago•1 comments

Microsoft expands direct competition with OpenAI and Anthropic

https://www.reuters.com/legal/litigation/microsoft-unveils-ai-models-coding-cybersecurity-it-take...
2•iotage•43m ago•0 comments

Why They Are Marrying Younger (1955)

https://www.nytimes.com/1955/01/30/archives/why-they-are-marrying-younger-uncertainties-about-the...
4•TMWNN•44m ago•0 comments

Interesting Learnings Working for a Startup

5•Jessiejia11•44m ago•1 comments

Optimizing AI Agents: Prompts vs. Weights (GEPA, GRPO) – Stanford CS329Z [video]

https://www.youtube.com/watch?v=e_m99aR7_3Q
2•matt_d•47m ago•0 comments

Intelligent machinery, a heretical theory – Alan Turing

https://turingarchive.kings.cam.ac.uk/publications-lectures-and-talks-amtb/amt-b-4
2•remywang•47m ago•0 comments

Harvard Study: Workers switch apps 900 times a day. After AI, switching drops

https://arxiv.org/abs/2607.06681
4•vaidsumer•50m ago•1 comments

Ignite 2026: Copilot is "the new OS for work," and now Office runs inside of it

https://arstechnica.com/gadgets/2026/11/microsoft-calls-copilot-the-new-os-for-work-at-ignite-key...
4•rlv-dan•53m ago•0 comments

Ask HN: Can world models lead to racisim? Are there any Alignment frameworks?

3•atul-mehra•58m ago•0 comments