3 ms·
A proof that Unix utility sed is Turing complete
- ethanholt1 3y agoA 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.
- gabrielsroka 3y agoI don't believe HTML is, but CSS is from what I've read.
- rmellow 3y agoWhy do we care if something is Turing complete? In other words, what are applications of Turing completeness?
- brokenmachine 3y agoIt 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 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 https://news.ycombinator.com/item?id=29568625
- coderatlarge 2y agoWith recent proposed regulations requiring real identity/kyc for IaaS, anything Turing complete served online is arguably included :)