我对什么是turing-machine和turing-complete语言有所了解,但是为了更好地理解,有人可以举出一些图灵不完整的语言示例吗? (也许甚至不是图灵机?)
最佳答案
在正式定义中,正则表达式仅包含:
只能识别常规语言。图灵完备的编程语言可以识别递归枚举的语言。
一个例子是,正则表达式不能告诉您字符串是否由匹配的括号对组成:例如,接受
()(())
而拒绝()((())()
,而图灵完备的编程语言可以接受。(请注意,现代编程语言中的正则表达式比正则表达式的正式学术定义更强大。有些甚至可能是图灵完整的。)