非图灵完备语言中的停机问题

Question

图灵完备语言的停机问题无法解决，但对于某些非图灵完备语言（例如正则表达式），其总是停机的停机问题可以轻松解决。

我想知道是否有一些语言既有停机又没有停机的能力，但却能够采用算法来确定它是否会停机。

- Shalmanese

---

你应该编辑标题，将其改为“图灵完备”; 起初我认为这是一个荒谬的问题（例如，“非图灵”=“不受我们关于图灵机等愚蠢定义的限制。”） - Domenic

Answer 1

停机问题不限于语言，而是针对机器（即程序）：它询问一个给定的程序在给定输入上是否停止。

也许您想问的是，它能否被解决应用于其他计算模型（例如您提到的正则表达式，还有下推自动机）。

在具有有限资源的模型中（如正则表达式或等价的有限状态自动机，其具有固定数量的状态和没有外部存储），通常可以检测到停机问题。这可以通过枚举所有可能的配置并检查机器是否进入同一配置两次（指示无限循环）轻松实现；对于有限资源，我们可以对在机器不停机之前必须看到重复配置的时间量进行上限估计。

通常，具有无限资源的模型（例如无限图灵机和下推自动机）不能进行停机检查，但最好分别研究这些模型及其开放性问题。

（对于所有维基百科链接表示抱歉，但它实际上是这类问题非常好的资源。）

- adrian

---

所有的机器都可以表示为它们接受的输入集合，即一种语言吗？ - FryGuy

@FryGuy：但你不能将这个信息提供给程序，因为那个表示是无限的。 - A. Rex

@A.Rex 但是你可以将停机问题表示为一种语言，该语言是所有停机程序的集合。 - Spudd86

Answer 2

是的。这类函数中一个重要的类别是原始递归函数。这个类别包括你期望能够用数字做的所有基本操作（加法、乘法等），以及像@adrian提到的一些复杂的类别（正则表达式/有限状态自动机，上下文无关文法/下推自动机）。然而，存在着一些不是原始递归的函数，例如阿克曼函数。

实际上，理解原始递归函数相当容易。它们是在没有真正递归（因此函数f不能直接或通过调用另一个函数g再调用f等方式调用自身）和没有while循环的编程语言中可以得到的函数，而是有界for循环。有界for循环是指像“for i从1到r”这样的循环，其中r是在程序中已经计算出来的变量；此外，在for循环中i不能被修改。这种编程语言的重点是每个程序都会停止。

我们编写的大多数程序实际上都是原始递归的（我的意思是可以转换为这样的语言）。

- A. Rex

---

等等，所以正则表达式是“总是停止”类型的（如OP所说），还是可能不会停止，但我们总是可以知道它是否停止？问这个问题是因为这个问题：https://dev59.com/_HM_5IYBdhLWcg3ww2AQ - agentofuser

我不确定我是否会说正则表达式实际上定义了一种计算模型。无论如何，总是可以在有限的时间内判断给定的字符串是否与给定的正则表达式匹配。 - A. Rex

Answer 3

简短的回答是可以，这样的语言甚至可以非常有用。几个月前在LtU上就此进行了讨论：http://lambda-the-ultimate.org/node/2846。

- Erik Engbrecht