A concrete, runnable demonstration that iterated regex…
0 reactions
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/
#technology
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/
#technology
| 1,000 mlx | |
| 2 | |
| 0 |