Are Perl regexes turing complete?

Question

I've seen Ruby and Perl programmers do some complicated code challenges entirely with regexes. The lookahead and lookbehind capabilities in Perl regexes make them more powerful than the regex implementations in most other languages. I was wondering how powerful they really are.

Is there an easy way to either prove or disprove that Perl regexes are Turing complete?

To those voting to close as off-topic: are these questions also off-topic? — Peter Olson
@PeterOlson: Yes, but they were asked before there was programmers.se — Daenyth
@daxim - What are the rules here? You can easily write a pattern for Rule 110 (for example, start with '010', and pattern s/(?:|(?<=0)(0)(?=0)|(?<=0)0(?=(1))|...|(?<=1)1(?=1)(?=1*(0))|^(?=(0))|(?<=(0))$)/$1/g - it needs some more thinking, I guess), but I think you need to use it in a loop to be of any use. Is that legitimate? Maybe you have a template of the program you're after? — Kobi
@Kobi If it's turing complete, it's legit. I don't really understand rule 110, so I don't know if that works or not. — Peter Olson

frezik frezik · Accepted Answer · 2011-11-02T20:11:06

Excluding any kind of embedded code, such as ?{ }, they probably don't cover all of context-free, much less Turing Machines. They might, but to my knowledge, nobody has actually proven it one way or another. Given that people have been trying to solve certain context-free problems with Perl regexes for a while and haven't come up with a solution yet, it's likely that they are not context-free.

There is an interesting discussion to be had about what features are merely convenient, and which actually add power. For instance, matching 0ⁿ*1*0ⁿ (that's notation for "any number of zeros, followed by a one, followed by the same number of zeros as before") is not something that can be done with pure regexes. You can prove this can't be done with regexes using the Pumping Lemma, but the simple, informal proof is that the regex would have to count an arbitrary number of zeros, and regexes can't do counting.

However, backreferences can match that with:

/(0*) 1 \1/x;

So that means backreferences give you more power, and are not a mere convenience. What else might give us more power, I wonder?

Also, Perl6 "patterns" (they're not even pretending they're regexes anymore) are designed to look kinda like Perl5 regexes (so you don't need to relearn much), but they have enough features added to be fully context-free. They're actually designed so you can use them to alter the way the language is parsed within a lexical scope.

Are Perl regexes turing complete?

3 Answers