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?
| [reply] |

Yes, you certainly were implementing essentially a type-0 grammar system the whole time. The point is that positively *identifying* it as a type-0 grammar gives a much clearer insight into your original question (do "plain" regex substitutions suffice to simulate Turing-complete behavior?) than going through SK/lambda as an intermediate step (which you found to require a little more care when simulating via regex substitutions). The theory of type-0 grammars says quite simply that there is a set of universal, plain regex substitution rules; in fact, as simple as you can imagine regex substitutions to be (s/fixed-string/fixed-string/). I didn't mean to imply that what you were doing was *not* an unrestricted grammar, just that we missed this "easiest" way to see the answer to that question in the original post.
| [reply] |

Thanks for clarifying—I think that I do take your meaning correctly now.
My issue comes with one subtle point, which is that, as you mention, we have a choice between incorporating a look-up table into our string, or using multiple substitutions; and the most naïve way of making use of the look-up table, as I did, turns the substitutions from `s/fixed/fixed/` to something involving capturing parentheses. My question was thus: Can we get the best (or “apparently least computationally powerful”) of both worlds, by having just one substitution, but not using anything but the ordinary (theoretical-CS, not Perl-enhanced) regular-expression constructs—in particular, no back-references—in it?
| [reply] [d/l] |