Re^4: Turing completeness and regular expressions

[JadeNB]

But we both missed the obvious way to just use "plain" regex substitutions to simulate Turing-completeness: unrestricted (type-0) grammars. They are basically defined as the repeated evaluation of plain regex substitutions, and are Turing-complete. A universal TM converted to a type-0 grammar will only have a finite number of substitution rules, and you can simulate it with a substitution + finite lookup table (or a finite # of separate s/// statements).

I didn't know about this, but I'm not sure that it's quite right to say that I missed it completely; indeed, the two wodges of code I wrote are just implementing systems of re-writing rules, which it seems to me are the same as unrestricted grammars, and the way that I did it is with a substitution plus a finite look-up table (built into the string on which the substitution acts). Am I missing your point?