问题标签 [halting-problem]

在课堂上，我们学习了停机问题，图灵机，归约等。很多同学说这些都是抽象无用的概念，了解它们没有任何意义（即，一旦课程结束就可以忘记它们）结束并且不会丢失任何东西）。

为什么理论有用？您是否曾经在日常编码中使用它？

您什么时候亲自遇到过该领域的停顿问题？这可能是当同事/老板提出一个违反计算基本限制的解决方案时，或者当你意识到你试图解决的问题实际上是不可能解决的。

我最近一次想到它是在学习类型检查器时。我们班意识到不可能编写一个完美的类型检查器（一个接受所有运行时没有类型错误的程序，并拒绝所有运行时出现类型错误的程序），因为这实际上可以解决停机问题. 另一个是当我们意识到，在同一个类中，在类型检查阶段不可能确定除以零是否会发生，因为在运行时检查一个数字是否为零也是停止问题的一个版本。

几乎所有使用的编程语言都是图灵完备的，虽然这提供了表示任何可计算算法的语言，但它也带来了自己的一系列问题。鉴于我编写的所有算法都打算停止，我希望能够用一种保证它们会停止的语言来表示它们。

词法分析时使用用于匹配字符串和有限状态机的正则表达式，但我想知道是否有一种更通用、更广泛的语言不是图灵完备的？

编辑：我应该澄清一下，通过“通用”我不一定希望能够用该语言编写所有停止算法（我认为这种语言不会存在）但我怀疑有共同的线程停止证明，可以推广以产生一种语言，其中所有算法都保证停止。

还有另一种方法可以解决这个问题——消除理论上无限内存的需要。一旦限制了机器允许的内存量，机器所处的状态数是有限且可数的，因此您可以确定算法是否会停止（通过不允许机器进入之前的状态） ）。

我用MATLAB 脚本语言编写了一个简单的脑筋急转弯解释器。它被提供随机 bf 程序来执行（作为遗传算法项目的一部分）。我面临的问题是，程序在相当多的情况下都会出现无限循环，因此 GA 会卡在这一点上。
因此，我需要一种机制来检测无限循环并避免在 bf 中执行该代码。
一个明显的（微不足道的）案例是当我有

我可以检测到这一点并拒绝运行该程序。
对于非平凡的情况，我发现基本思想是：确定循环的一次迭代如何改变当前单元格。如果变化是负的，我们最终会达到 0，所以这是一个有限循环。否则，如果更改为非负数，则为无限循环。
在单个循环的情况下实现这一点很容易，但是对于嵌套循环，它变得非常复杂。例如，（以下（1）指的是单元格1的内容等）

因此代码不断运行。然而，在单元格 1 上对 + 和 - 的数量进行简单检查会说 - 的数量更多，因此不会检测到无限循环。
给定 bf 中任意数量的循环的任意嵌套，谁能想到一个检测无限循环的好算法？

编辑：我确实知道停止问题通常是无法解决的，但我不确定是否不存在特殊情况例外。就像，也许 Matlab 可以充当超级图灵机，能够确定 bf 程序的停止。我可能大错特错，但如果是这样，我想确切地知道如何以及为什么。

第二次编辑：我写了我声称的无限循环检测器。它可能会遗漏一些边缘情况（或者不太可能，以某种方式逃脱图灵先生的魔掌），但到目前为止似乎对我有用。以伪代码形式，这里是：

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

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

我试图弄清楚如何为 Lua 编写自动完成算法，但是由于与许多脚本语言一样，它缺少静态类型系统，我认为我需要后台编译，但是在后台编译期间很容易遇到停止问题，所以我想知道以前是否有人解决过这种事情，解决编译和停止的标准策略是什么？

受这个问题的启发

假设我们有一个神奇的图灵机，它拥有无限的内存和无限的 CPU 能力。

发挥你的想象力，看看这怎么可能，例如它使用某种超空间连续体来自动并行化任何需要的东西，这样它就可以计算出任何可计算问题的答案，无论它的时间复杂度和数量是多少在一秒钟内完成实际的“逻辑步骤”。

但是，它只能在一秒钟内回答可计算的问题……所以我不是在假设一台“不可能”的机器（至少我不这么认为）……例如，这台机器仍然无法解决停机问题。

这种机器的编程语言会是什么样子？我目前所知道的所有编程语言都必须对“算法复杂性”做出一些让步……尽管消除了这种限制，但我希望我们所关心的只是编程语言的“表达能力”。即它能够简洁地表达“可计算的问题”......

无论如何，为了希望有趣的讨论，将其作为社区 wiki 开放......

每当人们询问与编程有关的停机问题时，人们都会回答“如果你只添加一个循环，你就会得到停机程序，因此你不能自动化任务”

说得通。如果您的程序有一个无限循环，那么当您的程序运行时，您无法知道程序是否仍在处理输入，或者它是否只是无限循环。

但其中一些似乎违反直觉。如果我正在编写一个以源代码作为输入的停机问题解决程序会怎样。rascher@localhost$ ./haltingSolver source.c

如果我的代码（source.c）如下所示：

我的程序似乎很容易看到这一点。“看看循环，看看条件。如果条件只是基于文字，没有变量，那么你总是知道循环的结果。如果有变量（例如 while (x < 10)），看看是否这些变量永远不会被修改。如果没有，那么你总是知道循环的结果。

当然，这些检查不会是微不足道的（计算指针算术等），但似乎并非不可能。例如：

可以被检测到。连同 - 尽管不是微不足道的：

现在用户输入呢？这就是踢球者，这就是使程序不可预测的原因。

现在我的程序可以说：“如果用户输入 10 或更大，程序将停止。在所有其他输入时，它将再次循环。”

这意味着，即使有数百个输入，也应该能够列出程序将停止的条件。确实，当我编写程序时，我总是确保有人能够终止它！我并不是说生成的条件列表很容易创建，但对我来说似乎并非不可能。您可以从用户那里获取输入，使用它们来计算指针索引等 - 但这只会增加条件数量以确保程序将终止，并不会导致无法枚举它们。

那么究竟什么是停机问题呢？关于我们不能编写问题来检测无限循环的想法，我有什么不明白的？或者，为什么“循环”是一个经常被引用的例子？

更新

所以，让我稍微改变一下这个问题：什么是适用于计算机的停机问题？然后我会回应一些评论：

很多人都说过，程序必须能够处理“任意输入”。但是在计算机中，从来没有任何任意输入。如果我只输入一个字节的数据，那么我只有 2^8 个可能的输入。所以，举个例子：

突然间，我刚刚考虑了所有的可能性。如果c位模式为 0x71，它会做一件事。对于所有其他模式，它会做其他事情。即使是接受任意字符串输入的程序也永远不会真正“任意”，因为资源是有限的，这意味着虽然“任意”理论适用……但它与实践并不完全是一对一的。

人们引用的另一个例子是：

如果 n 是一个 32 位整数......那么我可以直观地告诉你这是否会停止。

我想这个编辑没有问任何问题，但我见过的最有说服力的例子是这个：

假设您有您的神奇程序/方法来确定程序停止。

现在假设我们编写了一小段代码，例如...

所以对于这个例子，我们可以编写一个程序来做与我们神奇的停止方法完全相反的事情。如果我们以某种方式确定给定程序将停止，我们就会跳入无限循环；否则，如果我们确定程序处于无限循环中，则结束程序。

再说一次，如果你故意编写一个包含无限循环的程序......“解决停机问题”有点没有意义，不是吗？

对于某些输入字符串，是否有任何正则表达式可以永远搜索匹配项？

众所周知，停止问题没有明确的解决方案，a) 返回 true <==> 程序确实停止了，b) 处理任何输入，但我想知道是否有足够好的解决方案来解决这个问题，那些可能可以完美处理某些类型的程序流，或者能够识别何时无法正确解决问题的程序，或者正确率很高的程序，等等......

如果是这样，它们有多好，它们依赖什么想法/限制？