正则表达式通常被认为是不完善的语言的经典示例。例如，“正则表达式”作为这个 SO 问题的答案给出，寻找不是图灵完备的语言。
在我对转动完整性概念的理解中，这可能有点基本，这意味着不能使用正则表达式来检查“平衡”的模式。平衡的含义具有与结束字符相同数量的开始字符。这是因为这样做需要你有某种状态，以允许你匹配开始和结束字符。
然而，正则表达式的 .NET 实现引入了平衡组的概念。此构造旨在让您回溯并查看之前的组是否匹配。这意味着 .NET 正则表达式：
^(?<p>a)*(?<-p>b)*(?(p)(?!))$
可以匹配以下模式：
ab
aabb
aaabbb
aaaabbbb
... etc. ...
这是否意味着.NET 的正则表达式是图灵完备的？或者是否还有其他缺少的东西需要语言是图灵完备的？
在计算理论中，正则表达式描述了一种正则语言。正则语言类正是那些可以被某种有限状态机识别或由正则文法生成的语言。但是，您描述的示例（平衡短语）不是常规语言，无法被有限状态机识别或由常规语法生成。实际上，这是所谓的上下文无关语言的教科书示例。这些需要下推自动机进行识别。上下文无关语言类是常规语言的超集，但也是图灵完备语言的真子集。大多数编程语言的语法（与语义相反）是一种上下文无关的语言。如果您有兴趣了解有关此主题的更多信息，可以从乔姆斯基层次结构
.NET 中的正则表达式不是图灵完备的，因为它们总是停止。这对于一般的图灵机来说是不能说的。
你几乎错过了图灵完备的定义。
以艾伦·图灵命名的图灵完备性具有重要意义，因为迄今为止先进的计算设备的每一个合理设计都可以由通用图灵机模拟——这一观察已被称为 Church-Turing 论点。因此，可以作为通用图灵机的机器原则上可以执行任何其他可编程计算机能够执行的任何计算。然而，这与为机器编写程序所需的努力、机器执行计算所需的时间或机器可能拥有的与计算无关的任何能力无关。
现在，你不能在正则表达式中做某些事情，所以语言不完整。
你真的必须像其他人一样使用相同的定义，你知道的。有限的理解应该触发找出真相。
@Inuyasha：实际上您可以使用正则表达式进行加法。至少检查计算是否正确完成。唯一的事情是您必须以奇怪的顺序将输入提供给正则表达式（您不能使用正则表达式反转字符串（或检查它是否反转））。
模式是：
abc
def
---
ghi
=> cfi beh adg
假设您要在二进制中添加 1011 和 0110：
01011
00110
-----
10001
=> 101 110 010 100 001
如果您按照租约有效位到最大的顺序输入此输入，穿插第一个操作数、第二个操作数和输出，您将得到字符串 101110010100001。这可以通过以下方式匹配
((000|011|101)|(110(010|100|111)*001))*
这是一个花园品种正则表达式。您可以将其扩展到十进制加法，但正则表达式会变得非常复杂。