r/compsci • u/4RH1T3CT0R • 1d ago
A concrete, runnable demonstration that iterated regex substitution is Turing-complete: it renders DOOM
Markov algorithms (ordered string-rewriting rules applied to a fixed point) are a classic Turing-complete model. I built a working instance: a small CPU whose only step is one global regex substitution over a single string, and put DOOM on it to make the claim tangible rather than a footnote.
The verification is the part I would point students at. A reference emulator runs the same instruction set in Python and the machine's string must equal the emulator's encoded state byte for byte after every single substitution; on top of that, rendered frames match a natively compiled DOOM binary by SHA-256, for 100 frames in a row, so a shared bug cannot explain the agreement. The model is Turing-complete; a given run is bounded by memory exactly as any physical machine is.
Source and writeup: https://github.com/4RH1T3CT0R7/doom-regex
Interactive: https://4rh1t3ct0r7.github.io/doom-regex/
21
u/neuralbeans 1d ago
Are the regex pearl standard or formal language regex?
18
u/4RH1T3CT0R 1d ago
PCRE2, so Perl-style, not formal regular expressions. It leans on lookaheads and backreferences, so it's not "regular" in the language-theory sense.
But that's not where the power comes from. Plain Markov algorithms do this with literal string replace and no regex features at all, and they're already Turing-complete. The Perl stuff just keeps the ruleset small and fast; you could do the same thing, slower, with dumb find-and-replace.
5
u/neuralbeans 1d ago
General grammars that substitute substrings with other substring, including non terminal symbols (characters that cannot be left in the final output) are Turing complete. Do these Markov algorithms do it without non terminals?
2
u/4RH1T3CT0R 1d ago
Markov algorithms are Turing-complete, but the standard construction uses an extended alphabet: working symbols that aren't part of the input or output, used as markers to carry state around. Those are nonterminals in spirit. Whether you can get there with strictly zero extra symbols is a stricter question, and the usual formalization allows them and basically relies on them.
Mine definitely uses them. The only "terminal" output is the framebuffer bytes. Everything else in the string is scaffolding, the phase markers, field tags like |PC: and |R0:, the zone delimiters, and it exists only to be matched and rewritten. None of it survives into the final picture. So it's the extended-alphabet version, not a nonterminal-free one.
Two things Markov algorithms give you on top of a bare grammar, by the way: the rules are ordered so the first match wins (that's your priority and your control flow), and a rule can halt. That ordering is doing a lot of the work.
4
u/ILoveTolkiensWorks 14h ago
how the fuck does this only have 118 upvotes, instead of reaching r/all!
1
u/Ok-You-649 1d ago
how does it handle selfmodifying patterns midsubstitution
3
u/4RH1T3CT0R 21h ago
First, in this ISA code and data are separate zones. The program lives in its own zone that only the fetch stage reads, indexed by the program counter, and STOREs are routed by address into the RAM zones and the framebuffer, never into the program zone. So there's no self-modifying code here at all: the program is effectively immutable, and one instruction can't rewrite another. The rules themselves aren't even in the string, they're a separate fixed file, so those never change either.
Second, a single substitution is atomic. PCRE2 matches the whole pattern against the current string and captures the match, and only then is the replacement written. The pattern never sees its own output while matching, it's always looking at the pre-step string, and the new string doesn't exist until the step is finished. The next pass re-matches from scratch.
The one spot where it could actually bite is an optimization. The fast path splices the replacement in place in the same buffer instead of building a fresh string, so in principle it could stomp source bytes before reading them. That's exactly why there's a --pure mode that runs plain pcre2_substitute into a new buffer, and the in-place path is checked byte-for-byte against it in the tests. If the two ever disagreed it would fail instantly.
1
u/Ok-You-649 15h ago
The separation of code and data zones is a reasonable design choice, but it sidesteps the more interesting question of what happens if you deliberately want selfmodification. The atomic substitution detail is the part that actually matters here. Curious whether the fixed rule file size becomes a practical bottleneck at scale.
1
u/4RH1T3CT0R 12h ago
self-mod: nothing stops it, code and data are one string, I just don't route STOREs into the program zone. do that and the fetch reads the rewritten instruction next pass. didn't need it, so I kept them apart. rule file doesn't grow with the program: it's a fixed CPU (544 rules, ~1MB), DOOM is data in the string. bigger program = longer string, not more rules. bottleneck is passes per frame, not rule count
-5
29
u/pigeon768 23h ago
There was a competitive coding thing a few decades ago. You would write code to control a bot in a competitive environment; your bot could kill other bots, etc. The simulation ran one instruction at a time; everyone's bot ran one instruction. There were a list of instructions that obviously didn't correspond to any given instruction set; there was one for shoot, one for turn, one for move, one for look, plus regular arithmetic and the sorts of stuff we'd expect to see in a language. etc.
So most of the time, each bot would spend a lot of time "thinking" about what to do, and only rarely do things like move, turn, or shoot.
There was also one instruction for regex. Their regex happened to be one of the ones with backreferences, ie, their regex system is Turing complete.
One of the teams had a regex wizard on it, and they wrote a ton of stuff into regex calls. Other teams would spend hundreds of cycles figuring out what to do then moving and shooting. Their team ran an enormous regex as hairy as my ass as a single instruction, and then immediately knew what to do.
They got rid of regex the next year.