Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re^3: Turing completeness and regular expressions

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


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

You may be right about bottom-up evaluation of SK expressions. Larger terms must be treated as first-class objects to be passed around, etc.

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).

blokhead


Comment on Re^3: Turing completeness and regular expressions
Re^4: Turing completeness and regular expressions
by JadeNB (Chaplain) on Nov 28, 2009 at 18:00 UTC
    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?
      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.

      blokhead

        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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (16)
As of 2014-10-30 13:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (208 votes), past polls