3 ms·
Isn't this the same as Unix sed being Turing Complete? https://catonmat.net/proof-that-sed-is-turing-complete https://catonmat.net/proof-that-sed-is-turing-comp
by tooltower 4y ago
Isn't this the same as Unix sed being Turing Complete? https://catonmat.net/proof-that-sed-is-turing-complete https://catonmat.net/proof-that-sed-is-turing-complete
- pmayrgundter 4y ago"Turns out sed is a tiny assembly language that has a comparison operation, a branching operation and a temporary buffer. These operations make sed Turing complete." I studied CS, but nothing this succinct ever landed. Anyone have a good take on this?
- pmayrgundter 4y agoYeah, I suppose that's all a TM is.. comparison and branching on a symbol (a lot packed in there), and a temp buffer. Huh
- minitoar 4y agoIt’s one step up from a PDA, which has only a stack. A buffer you can r/w arbitrarily lets one compute things a stack won’t.
- pmayrgundter 4y agoAh, haven't heard PDA for years (besides the social;) For me the buffer is less.. like, you can buffer lots without processing. It's interesting that processing goes so simple. But i guess buffering is pretty essential.. like, you're implicitly creating a graph between the things buffered. Cool!
- tooltower 4y agoThat's pretty much it. It's notoriously easy to reach Turing Completeness without even trying. If you search for "Accidentally Turing Complete", you'll find several lists like this: https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html https://beza1e1.tuxen.de/articles/accidentally_turing_comple... I say "notorious" since this can often have negative implications for security.
- _8j50 4y agoIsn't even modern HTML turing complete?
- tambourine_man 4y agoCSS is. I don’t think pure HTML is.
- deleted 4y ago[deleted]