Do regex dream of Turing Completeness? (2021) [video] | Hacker News Reader

Do regex dream of Turing Completeness? (2021) [video]

youtube.com

Isn't this the same as Unix sed being Turing Complete? https://catonmat.net/proof-that-sed-is-turing-complete

"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?

Yeah, I suppose that's all a TM is.. comparison and branching on a symbol (a lot packed in there), and a temp buffer. Huh

It’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.

Ah, 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!

That'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_comple...

I say "notorious" since this can often have negative implications for security.

Isn't even modern HTML turing complete?

CSS is. I don’t think pure HTML is.

Pretty cool, he wrote a Turing machine using ruby regex. He also almost got a regex for the game of life.

It 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.

Is it that much of a stretch? {n} in regex for repeated patterns is already a construct, so let n->infinity.

Having 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

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).

I'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.

He admits that.

Even 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

His repo is here: https://github.com/dmagliola/regex_game_of_life

Reply on news.ycombinator.com