寻找图灵不完整的语言 [英] Looking for languages that are not Turing complete

问题描述

我对和turing-完整的语言，但为了更好地理解，有人可以举例说明图灵不完整的语言吗？ （也许甚至不是不是图灵机？）

I know a little about what is a turing-machine and a turing-complete language, but to understand better, could someone give examples of languages that are not Turing complete? (maybe even machines that are not Turing, as well?)

推荐答案

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

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

• 串联（ab）


• 无界重复（a *）


• 替代（a | b）


• 分组（（ab）|（cd））

• 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.)

这篇关于寻找图灵不完整的语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！