11–20 of 56 posts
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?
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:
(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)
Earlier quoted context omitted.
But... they are equivalent?
Modulo an exponential blowup! That’s like saying P is equivalent to NP.
im practice is a good idea to build a DFA from your regex, up front (re2) or lazily (ripgrep)
This is absurd. I did not realize you could do nearly this much computation in 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.
Earlier quoted context omitted.
But... they are equivalent?
Modulo an exponential blowup! That’s like saying P is equivalent to NP.
Earlier quoted context omitted.
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.
Earlier quoted context omitted.
But... they are equivalent?
Modulo an exponential blowup! That’s like saying P is equivalent to NP.
This is absurd. I did not realize you could do nearly this much computation in regex.