HN Theater @HNTheaterMonth

⬐ tingletech

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

⬐ zwkrt

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.

⬐ curiousgal

He admits that.

⬐ Hydraulix989

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

⬐ Hydraulix989

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

⬐ still_grokking

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

⬐ Hydraulix989

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.

⬐ morelisp

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

⬐ pmayrgundter

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

⬐ jdnier

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

⬐ tooltower

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

⬐ pmayrgundter

"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

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

⬐ minitoar

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.

⬐ pmayrgundter

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!

⬐ tooltower

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.

⬐ badrabbit

Isn't even modern HTML turing complete?

⬐ tambourine_man

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

⬐ zamadatix

HTML on its own isn't, same with CSS. They don't provide a way to execute arbitrary looping or actually "advance" any control flow without recomputing it. If you add interaction to states created by these (such as mouse/keyboard inputs) there are some tricks you can do, at least with CSS, but at that point it's not really HTML or CSS that are turning complete it's that plus some external stuff driving the system.