3 ms·
Do regex dream of Turing Completeness? (2021) [video]
- tingletech 4y agoPretty cool, he wrote a Turing machine using ruby regex. He also almost got a regex for the game of life.
- tooltower 4y agoIsn'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]
- deleted 4y ago[deleted]
- zwkrt 4y agoIt seems to me like he’s cheating in terms of Turing completeness because he has a loop that is running this regex over and over again.
- Hydraulix989 4y agoIs it that much of a stretch? {n} in regex for repeated patterns is already a construct, so let n->infinity.
- still_grokking 4y agoHaving a `while` loop (or unbounded recursion) is fundamentally more powerful than having only a `for` loop (or similar). https://en.wikipedia.org/wiki/BlooP_and_FlooP https://en.wikipedia.org/wiki/BlooP_and_FlooP So that's a big difference! (Actually the fundamental difference that can make a language Turing-complete in contrast to some other language that doesn't have the possibility to write an infinite loop).
- Hydraulix989 4y agoI'd imagine that regex has no practical use for an infinitely looped pattern, and that's why it was omitted. From an implementation standpoint, it's less of a stretch, but as you point out, it does mean it is now Turing Complete.
- deleted 4y ago[deleted]
- curiousgal 4y agoHe admits that.
- jdnier 4y agoHis repo is here: https://github.com/dmagliola/regex_game_of_life https://github.com/dmagliola/regex_game_of_life
- morelisp 4y agoEven sequential application of a regexp is substantially more powerful than you need to be general; you can do it with sequential application of static replacements until no match is found. https://en.wikipedia.org/wiki/Markov_algorithm https://en.wikipedia.org/wiki/Markov_algorithm