寻找非图灵完备的语言

Question

我知道一点什么是a 图灵机 和一个 图灵完备 语言，但为了更好地理解，有人可以举出非图灵完备的语言的例子吗？（甚至可能不是图灵机？）

Answer 1

正则表达式，在正式定义中，仅包含：

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

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

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

（请注意，现代编程语言中的正则表达式比正则表达式的正式学术定义更强大。有些甚至可能是图灵完备的。）

Answer 2

常规语言 - 那些可以被描述为正则表达式的 - 是 不图灵完备.

XML 和 JSON 等标记语言（用于描述数据，而不是计算）不是图灵完备的。