DOOM Runs on Regular Expressions, 180 Seconds Per Frame
The project proves regular expressions are Turing complete in practice, running a full game engine through a 32-bit virtual CPU built from string replacements.
Reporting from 1 source: GIGAZINE.
Programmer Artem Litkin released DOOM on regex, a project that runs the classic FPS using only regular expression search and replace. A 96.6 MB string holds the entire virtual machine, and 544 replacement rules execute the game. Rendering one frame takes about 180 seconds across five machines.
Artem Litkin's DOOM on regex stores the entire virtual computer, including the CPU registers, RAM, framebuffer, the DOOM engine, and WAD data, in one plain-text string of about 96.6 MB. A driver checks 544 replacement rules in fixed order, and each match rewrites part of the string, stepping the virtual machine.
The virtual CPU, named RVM-1, is a 32-bit design that operates solely on regex search and replace. The DOOM engine itself comes from doomgeneric, converted to RVM-1 instructions using the C compilers 8cc and ELVM. Rendering one frame requires about 13.99 million replacements across five machines, taking roughly 180 seconds.
Litkin notes the iteration of replacements is essentially a Markov algorithm, theoretically Turing complete. He says the real questions were whether it could finish before the heat death of the universe and how to prove no shortcuts were taken.
Synthesized by Yomimono from the 1 cited source below, including Japanese-language reporting where cited, then editorially reviewed before publishing.