停止在非图灵完备的语言

Question

在停机问题不能得到解决的图灵完备的语言，它可以为平凡一些非TC的语言，如正则表达式它总是停机来解决。

如果有同时具有停止和不停止的能力，但承认了一种算法，可以确定其是否停止任何语言我想知道。

Answer 1

是。这样的一类重要的是原始递归函数的。这个类包括所有的基本的东西，你希望能够用数字（加法，乘法等），以及一些复杂的类做这样@adrian提到（正则表达式/有限自动机，上下文无关文法/下推自动机）。有做，但是，存在不属于原始递归函数，如阿克曼函数。

这其实很容易理解的原始递归函数。他们说你可以得到在没有真正的递归（所以函数f不能调用自身，不管是直接还是通过调用另一个函数g是再调用f等），并没有while循环编程语言的功能，而不是已经有界的for循环。有界for循环是一个象“为i从1到R”，其中r是前面已经在程序中计算出的变量;另外，我不能在for循环内进行修改。这样的编程语言的一点是，每个的程序暂停。

我们写出大多数程序实际上是原始递归（我的意思是，可以被翻译成这样的语言）。

Answer 2

在停机问题不会对语言作用。相反，它作用于机 （即，程序）：它要求给定的程序是否停止在给定的输入

也许你的意思是问它是否可以解决的其他车型 计算（如正则表达式，你别说，还喜欢 下推自动机）。

停机可以，一般来说，可与有限的资源模型检测（如 正则表达式或等价地，有限自动机，它有一个固定的 状态数和没有外部存储）。这是很容易实现的 枚举所有可能的配置和检查机是否进入 相同的配置两次（表示无限循环）;有限 资源，我们可以把一个上限的时间量之前，我们必须见 一个重复的配置，如果机器不停止。

通常，具有无限资源模型（无界的TM和PDA，例如）， 不能停止核对，但它是最好的研究模型和 它们单独地打开的问题。

（对不起，所有的维基百科的链接，但它实际上是一个很好的资源 这种问题。）

Answer 3

简短的回答是肯定的，并且这样的语言甚至可以是非常有用的。

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