Take the 2-minute tour ×

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?

share|improve this question
See also cstheory.stackexchange.com/questions/1047/… –  KennyTM Nov 2 '11 at 15:48
Well, trivially, there is (?{ code }), so yes. I don't know the answer without the various experimental code-in-regexp features (the exclusion of which makes this non-trivial), so not leaving an answer. –  derobert Nov 2 '11 at 15:53
To those voting to close as off-topic: are these questions also off-topic? –  Peter Olson Nov 2 '11 at 16:10
@PeterOlson: Yes, but they were asked before there was programmers.se –  Daenyth Nov 2 '11 at 20:22
@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 Nov 9 '11 at 21:19

3 Answers 3

up vote 22 down vote accepted

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 0n*1*0n (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.

share|improve this answer

There are at least two discussions: Turing completeness and regular expressions and Are Perl patterns universal? with further references.

The consensus (to my untrained eye) seems to be that the answer is "no", but I am not sure if I understand everything correctly.

share|improve this answer

For regex'es in Perl there are two cases:

  1. With embedded code: They are of course turing complete.
  2. Without embedded code: They always halt so they are not general turing machines.

Every regular language can be accepted by a finite automaton. It's input must be a finite string.

[...] a deterministic finite automaton (DFA)—also known as deterministic finite state machine—is a finite state machine that accepts/rejects finite strings of symbols [...].

The same goes for Turing Machines: The formal definition does not even have input. It must be encoded in the finite number of states.

Alternative (equivalent) definitions include input, but it must be finite.

share|improve this answer
Will they always halt on arbitrary input, though? They won't always halt on an infinitely long string, for example. –  Miles Rout Jun 12 at 15:11
@MilesRout I don't think infinite input is allowed or makes sense. Almost nothing halts with infinite input. Even (ab)* does not halt because there can always be a c in the future. The text book answer is that regular languages are clearly not Turing complete. I think infinite input is just not part of the definition. –  usr Jun 12 at 15:24
(ab)* halts on infinite input like abcabcabcabcabcabc... –  Miles Rout Jun 13 at 3:45
Yeah, bad example. a*b does not halt for input aaaaa.... Anyway, I don't think infinite inputs are allowed or make sense. That would invalidate many important and clearly true results. –  usr Jun 13 at 10:58
@WilliamShipley infinite tape does not mean infinite input. Note again, that any machine of the Chomsky hierarchy does not halt if you feed infinite input to it. Therefore, it must be impossible to provide infinite input to make the existing definitions work. –  usr Aug 2 at 9:35

Your Answer


