computer-science - 寻找不是图灵完备的语言

Question

我对什么是图灵机和图灵完备的语言了解一些，但为了更好地理解，有人可以举一些不是图灵完备的语言的例子吗？（甚至可能不是图灵的机器？）

Answer 1

Regular expressions, in the formal definition, consisting only of:

• concatenation ( ab )
• unbounded repetition ( a* )
• alternation ( a|b )
• grouping ( (ab)|(cd) )

can only recognise regular languages. A Turing-complete programming language can recognise recursively-enumerable languages.

An example is that regular expressions cannot tell you if a string consists of matched pairs of parentheses: eg ()(()) is accepted while ()((())() is rejected, while Turing-complete programming languages can.

(Note that regexes in modern programming languages are more powerful than the formal academic definition of regular expressions. Some may even be Turing complete.)

Answer 2

正则语言——那些可以被描述为正则表达式的语言——不是图灵完备的。

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