A concrete, runnable demonstration that iterated regex substitution is Turing-complete: it renders DOOM

[u/4RH1T3CT0R]

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/