Perl 正则表达式图灵完备吗？

我见过 Ruby 和 Perl 程序员做了一些事情复杂的代码挑战 https://codegolf.stackexchange.com/questions/3596/regex-validating-regex完全用正则表达式。这前瞻和后瞻 http://www.regular-expressions.info/lookaround.htmlPerl 正则表达式中的功能使其比大多数其他语言中的正则表达式实现更强大。我想知道他们到底有多强大。

有没有一种简单的方法来证明或反驳 Perl 正则表达式图灵完备 https://stackoverflow.com/questions/7284/what-is-turing-complete?

排除任何类型的嵌入代码，例如?{ }，它们可能没有涵盖所有上下文无关的内容，更不用说图灵机了。他们可能会这么做，但据我所知，没有人真正以这种或那种方式证明过这一点。鉴于人们一直在尝试使用 Perl 正则表达式解决某些上下文无关问题，但尚未提出解决方案，因此它们很可能不是上下文无关的。

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.

但是，反向引用可以与以下内容相匹配：

/(0*) 1 \1/x;

因此，这意味着反向引用为您提供了更多功能，而不仅仅是一种便利。我想知道还有什么可以给我们更多的力量？

另外，Perl6“模式”（它们甚至不再假装它们是正则表达式）的设计看起来有点像 Perl5 正则表达式（因此您不需要重新学习太多），但它们添加了足够的功能来完全上下文 -自由的。实际上，它们的设计目的是让您可以使用它们来改变在词法范围内解析语言的方式。