Beefy Boxes and Bandwidth Generously Provided by pair Networks DiBona
No such thing as a small change

Re^4: Turing completeness and regular expressions

by JadeNB (Chaplain)
on Nov 28, 2009 at 18:00 UTC ( #809923=note: print w/ replies, xml ) Need Help??

in reply to Re^3: Turing completeness and regular expressions
in thread Turing completeness and regular expressions

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?

Comment on Re^4: Turing completeness and regular expressions
Re^5: Turing completeness and regular expressions
by blokhead (Monsignor) on Nov 28, 2009 at 18:20 UTC
    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.


      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?

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://809923]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (9)
As of 2014-04-17 22:15 GMT
Find Nodes?
    Voting Booth?

    April first is:

    Results (458 votes), past polls