Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.
(In terms of Regexes, Javascript has a very rich Turing complete Regex library; it’s an open question whether Lua 5.1’s regexes are Turing complete, but they are good enough for the text processing I do)
The technical write up is worth perusing but I played a game before reading and accidentally found a winning strategy immediately. I'm not sure if this is a result of the 2-ply nature of the engine or if the mentioned deficiencies account for this but the computer did not act to prevent checkmate in 1 (without any intervening check); the game I played was (in algebraic notation):
1. e4 e5
2. kf3 kf6
3. kxe5 kxe4
4. d4 kxf2
5. Kxf2 a5
6. Qf3 b5??
7. Qxf7
1-0
Upon reading the title, this is one of those "I know that's possible, but I'd never bother to implement it" things, although this particular implementation isn't exactly what I had in mind.
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.
23 comments:
This is amazing. I'm at loss for words.
During my CS years I remember being fascinated by NFA's, as opposed to boring single universe DFA's.
For some reason I internalized that I would never see something like an NFA implemented beyond text books.
Then came Carlini.
But... they are equivalent?
Modulo an exponential blowup! That’s like saying P is equivalent to NP.
Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.
Running NFA is O(nm) not NP.
No, because you can compute the optimal automaton (as in least number of states) that recognizes the same language: https://en.wikipedia.org/wiki/DFA_minimization
And there are language families where minimal DFA is still exponentially large compared to NFA.
The blow up is exponential for carefully crafted academical regular expressions.
im practice is a good idea to build a DFA from your regex, up front (re2) or lazily (ripgrep)
For people who are interested, here is the solution. In standard PGN, the solution is:
1. e4 e5 2. Nf3 Nf6 3. Nxe5 Nxe4 4. Qe2 Nxd2 5. Nc6+ Ne4 6. Nxd8 Kxd8 7. Qxe4 a6 8. Bg5+ Be7 9. Qxe7#
In the Stockfish notation this engine uses, White’s moves are:
1. e2e4 2. g1f3 3. f3e5 4. d1e2 5. e5c6 6. c6d8 7. e2e4 8. c1g5 9. e4e7
Here is a Lichess analysis of this game:
https://lichess.org/WnMF3LpX
(In terms of Regexes, Javascript has a very rich Turing complete Regex library; it’s an open question whether Lua 5.1’s regexes are Turing complete, but they are good enough for the text processing I do)
The technical write up is worth perusing but I played a game before reading and accidentally found a winning strategy immediately. I'm not sure if this is a result of the 2-ply nature of the engine or if the mentioned deficiencies account for this but the computer did not act to prevent checkmate in 1 (without any intervening check); the game I played was (in algebraic notation): 1. e4 e5 2. kf3 kf6 3. kxe5 kxe4 4. d4 kxf2 5. Kxf2 a5 6. Qf3 b5?? 7. Qxf7 1-0
This is like a fever dream.
Brilliant. The Chinese room thought experiment as a chess engine.
Upon reading the title, this is one of those "I know that's possible, but I'd never bother to implement it" things, although this particular implementation isn't exactly what I had in mind.
"Memory plus search is all you need"
2025
And now you have 84,689 problems
Previously posted: https://news.ycombinator.com/item?id=42619652
This is absurd. I did not realize you could do nearly this much computation in regex.
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
Alternate title:
Compiling Python to a Branch-Free SIMD Virtual Machine via Extended Regular Expression String Rewriting