Hacker News new | ask | show | jobs
by devanshp 32 days ago
This is absurd. I did not realize you could do nearly this much computation in regex.
3 comments

It's not just regex. The regular expressions are used to select and perform an action. There's a loop around it with controls the stack. That has more power than the regex.
It’s turing complete so you could compile almost any language to regex. You might have to build a vm for some languages, also in regex. The point is, it’s regex all the way down.
Regular expressions are not Turing-complete.
True in the CS Theory space, but most modern regex engines implement a few niceties which make their "regex" turing complete. https://blog.poisson.chat/posts/2024-06-18-turing-regex.html
Javascript/PCRE/etc regexes have additional features (like backreferences) that give them strictly more computational power than a regular DFA/NFA. (Still not Turing complete though without external control flow to support arbitrary iteration/recursion, like is done here)
This is an odd comment because it's a famously (imo) over known fact due to cs textbooks and how academia organizes knowledge, optimizing for pushing papers over genuine discovery.