Mastering Regular Expressions 2nd Ed.

[Paul Rubin]

Michael Hudson <mwh at python.net> writes:
> > I may be wrong about this, but I don't think regular expressions
> > qualify as turing complete. No branching for one thing...
> 
> Somewhere you can find a (perl) regexp that matches prime but not
> composite numbers, which suggests Turing completeness -- and rather
> takes the mickey out of the word "regular".

Formally, regular expressions can be recognized by finite state
machines, thus no hope of recognizing primes.

Perl regexps aren't really regexps because of the tricks you can play
with back-substitution etc.  They're a superset of traditional regexps.