Welcome to the Monastery  
PerlMonks 
Are Perl patterns universal?by sleepingsquirrel (Hermit) 
on Nov 09, 2004 at 01:27 UTC ( #406253=perlmeditation: print w/ replies, xml )  Need Help?? 
or Why compute with anything else? Lately I've been wondering about just how powerful Perl's pattern matching language is (commonly known as regular expressions). Because of backtracking and recursion, Perl's patterns can match more than regular languages. They can match (at least some) contextfree grammars......they can also match (at least some) context sensitive grammars... (I've haven't proven those two snippets correct, so any counter examples would be appreciated) We can also craft patterns that loop forever (not merely a long time) (well, ignoring stack overflows that is) On a more mundane level we can also compute simple things... It is also known that certain cellular automata are universal (Rule 110), and with some additional machinery, we can get a regex to emulate one. Of course that might be considered cheating, because we've used an external mechanism for looping. It gets more interesting when we consider that some Diophantine equations are universal . And a few perl wizards have managed to use regex to solve linear Diophantine equations and test for primeness (see also section 6.16 of the Ram book). Your mission, should you choose to accept it, is to meditate on this problem and see if you can enlighten the rest of us as to whether perl5 patterns are universal. (Or, as a lesser challenge, see if you can get a regex to compute 2**N, or factorial(N), or Ackermann's function)  All code is 100% tested and functional unless otherwise noted.
Back to
Meditations

