寻找非图灵完备的语言
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?)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
正则表达式，在正式定义中，仅由以下组成：
只能识别正则语言。图灵完备的编程语言可以识别递归可枚举语言。
一个例子是，正则表达式无法告诉您字符串是否由匹配的括号对组成：例如
()(())被接受，而()((())() 被拒绝，而图灵完备的编程语言可以（请注意，现代编程语言中的正则表达式比正则表达式的正式学术定义更强大。有些甚至可能是图灵完备的。）
Regular expressions, in the formal definition, consisting only of:
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.)
常规语言 - 那些可以描述为正则表达式的语言 - 是 非图灵完备。
XML 和 JSON 等标记语言（用于描述数据，而不是计算）不是图灵完备的。
Regular languages - those that can be described as regular expressions - are not Turing complete.
Markup languages (used for describing data, not computation) like XML and JSON are not Turing complete.