寻找非图灵完成的语言

我对turing-machine和turing-complete语言有一点了解，但为了更好地理解，有人可以给出非图灵完整语言的示例吗？（也许甚至不是图灵的机器呢？）寻找非图灵完成的语言

来源

2010-08-30 Tom Brito

正则表达式，在正式的定义，只包括：

级联（AB）
无限重复（A *）
交替（A | B）
分组（（ ab）|（cd））

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

一个例子是，正则表达式不能告诉你，如果一个字符串由匹配的括号对组成：例如()(())被接受，而()((())()被拒绝，而图灵完全编程语言可以。

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

来源

2010-08-30 12:42:04

例如，Perl regexp可以递归：http://www.catonmat.net/blog/recursive-regular-expressions PHP regexp具有/ e标志来评估替换中的PHP表达式。 – 2010-08-31 17:13:16

@SHi：谢谢你，非常有趣！ – 2010-08-31 17:47:55

在Perl中看到一个正则表达式，它匹配的长度仅为质数的字符串。使用回溯并花了相当长一段时间... – 2010-09-27 15:57:41

Regular languages - 那些可以被描述为正则表达式的 - 是not Turing complete。

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

来源

2010-08-30 12:37:58

数据和计算之间的差别是非常棘手。 [LaTeX]（http://stackoverflow.com/questions/2968411/ive-heard-that-latex-is-turing-complete-are-there-any-programs-written-in-latex）是图灵完整的，尽管是一种文本处理语言。 – 2010-08-30 12:43:09

@Phillip：不完全公平，因为LaTeX可以访问所有TeX（至少部分）是通用语言。见Knuth的页面，他在那里回答“你最喜欢的语言是什么？”的问题。 – Charles 2010-09-01 02:56:59

寻找非图灵完成的语言

回答

相关问题