停止使用非图灵完整语言

对。这类的一个重要类是 primitive recursive functions . 这个类包括了所有你希望能用数字(加法、乘法等)做的基本事情,以及一些复杂的类,如@adrian已经提到过的(正则表达式/有限自动机、上下文无关语法/下推自动机)。但是,存在一些不是原始递归的函数,例如 Ackermann function .

实际上很容易理解原始递归函数。它们是在没有真正递归的编程语言中可以得到的函数(因此函数f不能直接或通过调用另一个调用f的函数g来调用自身),并且没有while循环,而是有界f or循环。有界for循环类似于“for i from 1 to r”,其中r是一个已经在程序早期计算过的变量;而且,在for循环中不能修改i。这种编程语言的要点是 每一个 程序暂停。

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

这个 halting problem 不适用于语言。相反,它作用于机器 (即程序):它询问给定程序是否在给定的输入上停止。

也许你想问一下,对于其他的模型,它是否可以被解决。 计算(像你提到的正则表达式,但也像 push-down automata )

通常,在资源有限的模型中可以检测到暂停(如 正则表达式或具有固定 状态数,没有外部存储)。这很容易通过 枚举所有可能的配置并检查计算机是否进入 相同配置两次(表示无限循环);有限 资源,我们可以在 必须 看见 机器不停机时的重复配置。

通常,具有无限资源的模型(例如,无限TMS和PDA) 不能停止检查,但最好调查模型和 他们各自面临的问题。

(对维基百科的所有链接都感到抱歉,但它实际上是一个很好的资源 这类问题。)

简短的回答是肯定的,这样的语言甚至非常有用。

几个月前有一个关于LTU的讨论: http://lambda-the-ultimate.org/node/2846