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

How image generation got good (diffusion derivations)

https://shuklabhay.github.io/gallery/diffusion/
1•01shuklabhay•2m ago•0 comments

Tech leaders are convinced that Jensen Huang's exit was a plot against him

https://www.theverge.com/tech/1035027/tech-leaders-nvidia-jensen-huang-theories
4•madihaa•6m ago•1 comments

Deep Personalization: Unlocking Personalized Proactive Agents with Local Compute

https://nvlabs.github.io/deep-personalization/
1•matt_d•8m ago•0 comments

Microsoft Post-Incident Report Is Up for the Exchange Online Outage

https://www.reddit.com/r/sysadmin/comments/1xxiasy/microsoft_postincident_report_is_up_for_the/
3•vismit2000•8m ago•0 comments

Gone Fishin': The Answer to JensenGate Is the Pond Principle

https://www.pond.is/p/gone-fishin-the-answer-to-jensengate
1•StevenVincent•15m ago•0 comments

Robot Learning

https://robotlearningbook.com/
1•gmays•17m ago•0 comments

Memory Poker

https://juileebhosale.com/memory-poker
1•dropbox_miner•22m ago•0 comments

GitHub Copilot models deprecated on November 16, 2026

https://github.blog/changelog/2026-11-16-github-copilot-models-deprecated-on-november-16-2026/
3•axis_official•25m ago•2 comments

I Rebuilt Google Drive on GitHub

https://adventuresinclaude.ai/posts/i-rebuilt-google-drive-on-github
1•aanet•28m ago•0 comments

Show HN: MillionShort – A search engine you can remove 1M sites

https://millionshort.com/
1•taxonomyman•28m ago•0 comments

I Love "Elizabeth Holmes"

https://sidneynotsydney.substack.com/p/i-love-elizabeth-holmes
1•wmchen•34m ago•0 comments

Saturn Devouring His Sun

https://en.wikipedia.org/wiki/Saturn_Devouring_His_Son
2•wasabi991011•38m ago•0 comments

Show HN: Apple's apps never reached Android. Built in Rust

https://github.com/YashwanthKamireddi/Skykeep
1•YashOnYC•42m ago•0 comments

The whole world is long America

https://www.ft.com/content/1f1a2a9b-9429-4e4b-8606-7be8a1fd701e
3•jmeister•43m ago•0 comments

Nvidia Board Warned of 'Irreplaceable' Talent Loss in Employee Letter

https://www.wsj.com/business/nvidia-board-warned-of-irreplaceable-talent-loss-in-employee-letter-...
3•bryan0•46m ago•1 comments

Towering waterspouts spotted over San Francisco Bay

https://www.sfgate.com/bayarea/article/waterspouts-sf-bay-video-22534057.php
1•kaycebasques•48m ago•0 comments

A Modular, Extensible, Serving System for Multimodal Models

https://mstar.stanford.edu/
2•groodt•50m ago•0 comments

Bunnings to make 230 jobs redundant amid partial offshoring of tech services

https://www.abc.net.au/news/2026-11-17/bunnings-layoffs-and-offshoring/107394860
5•langfo•53m ago•0 comments

Ask HN: Where are you on the spectrum of AI/LLM adoption?

1•joddystreet•56m ago•2 comments

Last year we built megakernels. This year we deleted them: The road to TKCC

https://www.together.ai/blog/road-to-together-compiler
1•matt_d•1h ago•0 comments

File over App (2023)

https://stephango.com/file-over-app
1•theanonymousone•1h ago•0 comments

Devi: App is live. Now find the first customers

https://devi.devz.ai/signup?utm_source=hackernews&utm_medium=hnpost&utm_campaign=hnpost111326
1•devzai•1h ago•0 comments

From One Sentence to a Running Pipeline

https://altertable.ai/blog/2026-11-16-from-one-sentence-to-a-running-pipeline
1•mooreds•1h ago•0 comments

Show HN: Blobby – A design canvas that Claude, Cursor or Codex drives over MCP

https://useblobby.com/
1•bisht3404•1h ago•0 comments

I tried to make it with Claude and now it is monitize

https://namecombiner.io/
1•jason66•1h ago•0 comments

Systemd Loves Rust

https://amutable.com/blog/systemd-loves-rust
2•mooreds•1h ago•0 comments

Show HN: FocusBlock – a local-first website blocker for Edge

https://microsoftedge.microsoft.com/addons/detail/focusblock/kdpeddhiegpfadpjiaieoaeiloebgdhp
1•alapha888•1h ago•0 comments

Agentic AI Attacks Nobody's Talking About (Yet)

https://glyphzerolabs.com/blog/2026-04-17-agentic-ai-attacks/
1•mooreds•1h ago•0 comments

Visual particle application, instantly relax your mood

https://www.reddit.com/r/iosapps/comments/11y0cpi/visual_particle_application_instantly_relax_your/
2•lucakk•1h ago•0 comments

Show HN: A Glimpse of the Particle World

https://nonloop.github.io/dancingparticle/
1•lucakk•1h ago•0 comments