Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re^6: Turing completeness and regular expressions

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


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

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?


Comment on Re^6: Turing completeness and regular expressions
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (11)
As of 2015-07-30 22:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (273 votes), past polls