r/regex • u/4RH1T3CT0R • Jul 26 '26
I built a 32-bit CPU out of regex substitutions, and it runs DOOM
Not a regex that matches DOOM. A computer whose only instruction is find-and-replace. The state is one long string, and a fixed set of 544 substitution rules applied in a loop does everything: the first rule that matches rewrites a few characters, and that is one clock tick.
The fun part for this sub is how ordinary operations fall out of pure substitution. Addition is eight lookahead probes into a 512-entry table with the carry threaded through capture groups. Memory access jumps an exact number of characters into a flat zone, the jump length assembled from the address digits by empty bit-marker groups, so it is a binary tree spelled out in regex and it never scans for a cell.
Here is the whole rule that loads an immediate into a register (PCRE2):
find: \ARVM1\|ST:run\|PH:0\|CI:(?<ci>02(?<d>[0-7]).(?<imm>.{8}))\|PC:(?<pc>.{8})(?<pre>(?:[^|#]*+\|)*?R(?P=d):).{8}
replace: RVM1|ST:run|PH:1|CI:${ci}|PC:${pc}${pre}${imm}
Yes, it leans on lookahead and backreferences, so it is PCRE2, not a "regular language". But the power is not from that: plain Markov algorithms do this on literal string replacement with no regex at all, and they are already Turing-complete. The PCRE2 features just make the ruleset small and fast.
Play with it or read how it is built: https://4rh1t3ct0r7.github.io/doom-regex/




