Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Re^5: Turing completeness and regular expressions

by blokhead (Monsignor)
on Nov 28, 2009 at 18:20 UTC ( #809926=note: print w/replies, xml ) Need Help??

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

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.


  • Comment on Re^5: Turing completeness and regular expressions

Replies are listed 'Best First'.
Re^6: Turing completeness and regular expressions
by JadeNB (Chaplain) on Nov 28, 2009 at 18:34 UTC

    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://809926]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2017-09-20 02:37 GMT
Find Nodes?
    Voting Booth?
    During the recent solar eclipse, I:

    Results (230 votes). Check out past polls.