Hacker News new | past | comments | ask | show | jobs | submit login
A proof that Unix utility sed is Turing complete (catonmat.net)
15 points by sebmellen on April 28, 2024 | hide | past | favorite | 5 comments



A lot of things that you wouldn’t expect to be Turing complete are. Magic the Gathering, the video game Terraria, and HTML, to name a few.


I don't believe HTML is, but CSS is from what I've read.


Why do we care if something is Turing complete? In other words, what are applications of Turing completeness?


It means that you can basically program it to do anything.

ie you could create a Virtual Machine running inside sed that could run Windows or anything else.

https://en.wikipedia.org/wiki/Turing_completeness

>In colloquial usage, the terms "Turing-complete" and "Turing-equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate the computational aspects of any other real-world general-purpose computer or computer language.

Interesting sidenote: there's an NSO iPhone exploit that created it's own virtual machine inside an image decoder.

Basically they took a buffer overflow and used it to create a whole turing complete virtual machine.

It's insane. https://news.ycombinator.com/item?id=29568625


With recent proposed regulations requiring real identity/kyc for IaaS, anything Turing complete served online is arguably included :)




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: