寻找不是图灵完整的语言

Question

我知道什么是图灵机和图灵完整的语言,但为了更好地理解,有人可以提供非图灵完整语言的例子吗？(甚至可能是不是图灵的机器？)

Answer 1

正式定义中的正则表达式,仅包含:

• 连接(ab)
• 无限重复(a*)
• 交替(a | b)
• 分组((ab)|(cd))

只能识别常规语言.图灵完备的编程语言可以识别递归可枚举的语言.

一个例子是正则表达式无法告诉您字符串是否由匹配的括号对组成:例如()(()),()((())()被拒绝时接受,而图灵完整编程语言可以.

(请注意,现代编程语言中的正则表达式比正则表达式的正式学术定义更强大.有些甚至可能是图灵完成的.)