停止使用非图灵完整的语言

暂停问题对于图灵完整语言是无法解决的,并且对于一些非TC语言(例如它总是停止的正则表达式),它可以简单地解决.

我想知道是否有任何语言都具有停止和不停止的能力,但允许一种算法可以确定它是否停止.

该停机问题不作用于语言.相反,它作用于机器(即程序):它询问给定程序是否在给定输入上停止.

也许你想问一下它是否可以解决其他计算模型(比如你提到的正则表达式,还有 下推自动机).

通常,可以在具有有限资源的模型中检测停止(如正则表达式,或者等效地,有限自动机,其具有固定数量的状态且没有外部存储).这可以通过枚举所有可能的配置并检查机器是否进入两次相同的配置(表示无限循环)来轻松完成; 在资源有限的情况下,如果机器没有停止,我们可以在必须看到重复配置之前的时间量上限.

通常,具有无限资源的模型(例如,无限制的TM和PDA)无法停止检查,但最好分别调查模型及其开放问题.

(对不起所有的维基百科链接,但它实际上是这类问题的一个非常好的资源.)

是.这种类型的一个重要类是原始递归函数.这个类包括你期望能够用数字做的所有基本的东西(加法,乘法等),以及像@adrian所提到的一些复杂类(正则表达式/有限自动机,无上下文语法/下推)自动机).但是,存在不是原始递归的函数,例如Ackermann函数.

实际上,理解原始递归函数非常容易.它们是你可以在没有真正递归的编程语言中获得的函数(因此函数f不能直接调用自身,或者通过调用另一个函数g然后调用f等)并且没有while循环,而是有限制的循环.有界for循环就像"for i from 1 to r",其中r是一个已经在程序中早先计算过的变量; 另外,我不能在for循环中修改.这种编程语言的意义在于每个程序都会停止.

我们编写的大多数程序实际上是原始的递归(我的意思是,可以翻译成这样的语言).

简短的回答是肯定的,这些语言甚至可以非常有用.

几个月前在LtU上讨论过它:http://lambda-the-ultimate.org/node/2846