title: Are Perl regexes turing complete?
body: <p>I've seen Ruby and Perl programmers do some <a href="https://codegolf.stackexchange.com/questions/3596/regex-validating-regex">complicated code challenges</a> entirely with regexes. The <a href="http://www.regular-expressions.info/lookaround.html" rel="noreferrer">lookahead and lookbehind</a> capabilities in Perl regexes make them more powerful than the regex implementations in most other languages. I was wondering how powerful they really are.</p>
  
  <p>Is there an easy way to either prove or disprove that Perl regexes are <a href="https://stackoverflow.com/questions/7284/what-is-turing-complete">Turing complete</a>?</p>