您什么时候亲自遇到过该领域的停顿问题？这可能是当同事/老板提出一个违反计算基本限制的解决方案时，或者当你意识到你试图解决的问题实际上是不可能解决的。
我最近一次想到它是在学习类型检查器时。我们班意识到不可能编写一个完美的类型检查器（一个接受所有运行时没有类型错误的程序，并拒绝所有运行时出现类型错误的程序），因为这实际上可以解决停机问题. 另一个是当我们意识到，在同一个类中，在类型检查阶段不可能确定除以零是否会发生，因为在运行时检查一个数字是否为零也是停止问题的一个版本。
Claudiu
问问题
5610 次
13 回答
60
我确实被分配了停止问题，例如“编写监视器插件以确定主机是否永久关闭”。严重地？好的，所以我会给它一个阈值。“不，因为它可能会在之后重新出现。”
大量的理论阐述随之而来。
于 2008-10-25T06:13:45.900 回答
44
几年前，我记得读过一篇名为 Basic Infinite Loop Finder 或 BILF 的产品的评论（我相信是在 Byte 杂志上）。BILF 应该扫描您的 Microsoft Basic 源代码并找到任何未终止的循环。它声称能够在代码中找到任何无限循环。
审稿人非常精明地指出，要使该程序在所有情况下都能正常工作，它必须解决停机问题，并且甚至提供了一个数学证明来证明它为什么不能在所有情况下工作。
在下一期中，他们发表了公司代表的一封信，解释说该问题将在下一版本中得到解决。
更新：我在 imgur 上看到了这篇文章的图片。我记错杂志了。是创意计算，而不是字节。否则，这和我记忆中的差不多。
你可以在imgur上看到它的高分辨率版本。
于 2009-01-23T13:16:09.573 回答
35
我现在正在做的项目到处都是无法确定的问题。它是一个单元测试生成器，所以通常它试图完成的是回答“这个程序做什么”这个问题。这是停止问题的一个实例。开发过程中出现的另一个问题是“两个（测试）功能是否相同”？甚至“这两个调用（断言）的顺序是否重要”？
这个项目的有趣之处在于，即使你不能在所有情况下都回答这些问题，但你可以找到 90% 的时间解决问题的智能解决方案，这对于这个领域来说实际上是非常好的。
尝试推理其他代码的其他工具，如优化编译器/解释器、静态代码分析工具，甚至重构工具，可能会遇到（因此被迫寻找解决方法）停止问题。
于 2008-10-25T06:37:51.983 回答
30
示例 1. 我的报告有多少页？
当我学习编程时，我玩弄了一个从数据中打印出漂亮报告的工具。显然我希望它非常灵活和强大，因此它将成为结束所有报告生成器的报告生成器。
报告定义最终变得如此灵活，以至于它是图灵完备的。它可以查看变量，在备选方案之间进行选择，使用循环来重复事情。
我定义了一个内置变量 N，即报表实例中的页数，因此您可以在每页上放置一个表示“第 n 页”的字符串。我做了两次，第一次计算页面数（在此期间 N 设置为零），第二次使用从第一遍获得的 N 实际生成它们。
有时第一遍会计算 N，然后第二遍会生成不同数量的页面（因为现在非零 N 会改变报告所做的事情）。我尝试迭代地进行传递，直到 N 稳定下来。然后我意识到这是没有希望的，因为如果它没有安定下来怎么办？
这就引出了一个问题，“如果迭代永远不会确定他们报告产生的页数的稳定值，我至少可以检测并警告用户吗？” 幸运的是，此时我已经对阅读图灵、哥德尔、可计算性等产生了兴趣，并建立了联系。
多年后，我注意到 MS Access 有时会打印“第 6 页，共 5 页”，这真是一件了不起的事情。
示例 2：C++ 编译器
编译过程涉及扩展模板。模板定义可以从多个特化中选择（足以充当“条件”），它们也可以是递归的。所以它是一个图灵完备的（纯函数式）元系统，其中模板定义是语言，类型是值，编译器实际上是一个解释器。这是一个意外。
因此，不可能检查任何给定的 C++ 程序并判断编译器原则上是否可以在成功编译该程序时终止。
编译器供应商通过限制模板递归的堆栈深度来解决这个问题。您可以在 g++ 中调整深度。
于 2008-12-02T17:27:44.027 回答
21
很多个月前，我正在协助我们公司的一位顾问，他正在实施一个非常复杂的轨道系统，将金属零件篮子移入和移出 1500 度的高炉。轨道本身是车间里一个相当复杂的“迷你铁路场”，在几个地方相交。几个电动托盘会根据时间表在周围穿梭一篮子零件。尽可能短的时间打开炉门是非常重要的。
由于工厂处于全面生产状态，顾问无法“实时”运行他的软件来测试他的调度算法。相反，他编写了一个漂亮的图形模拟器。当我们看到虚拟托盘在他的屏幕轨道布局上移动时，我问“你怎么知道你是否有任何调度冲突？”
他的回答很快，“简单——模拟永远不会停止。”
于 2008-11-20T21:12:02.890 回答
13
复杂的静态代码分析可能会遇到停机问题。
例如，如果 Java 虚拟机可以证明一段代码永远不会越界访问数组索引，它可以省略检查并运行得更快。对于某些代码，这是可能的；随着它变得越来越复杂，它变成了停止问题。
于 2008-10-25T06:24:41.837 回答
11
这对于 GPU 应用程序中的着色器来说仍然是一个问题。如果着色器有一个无限循环（或一个很长的计算），驱动程序应该（在某个时间限制后）停止它，杀死片段，还是让它运行？对于游戏和其他商业内容，前者可能是您想要的，但对于科学/GPU 计算，后者才是您想要的。更糟糕的是，某些版本的 windows 假设由于图形驱动程序已经有一段时间没有响应，它会杀死它，这在 GPU 上进行计算时人为地限制了计算能力。
应用程序没有 API 可以控制驱动程序的行为或设置超时等，而且驱动程序当然无法判断着色器是否会完成。
我不知道这种情况最近是否有所改善，但我想知道。
于 2008-11-21T22:59:17.727 回答
6
另一个常见的版本是“我们需要消除多线程代码中的任何死锁”。从管理的角度来看，这是一个完全合理的请求，但是为了防止在一般情况下出现死锁，您必须分析软件可能进入的每个可能的锁定状态，这毫不奇怪，相当于停机问题。
有一些方法可以通过在锁定之上施加另一层（如定义的获取顺序）来部分“解决”复杂系统中的死锁，但这些方法并不总是适用。
为什么这相当于停机问题：
假设你有两个锁，A 和 B，以及两个线程，X 和 Y。如果线程 X 有锁 A，也想要锁 B，而线程 Y 有锁 B，也想要 A，那么你就有了死锁。
如果 X 和 Y 都可以访问 A 和 B，那么确保您永远不会进入错误状态的唯一方法是确定每个线程可以通过代码采取的所有可能路径，以及它们的顺序在所有这些情况下都可以获取并持有锁。然后确定两个线程是否可以以不同的顺序获取多个锁。
但是，确定每个线程可以通过代码采取的所有可能路径（在一般情况下）等同于停机问题。
于 2008-11-20T20:55:02.987 回答
5
Perl 的测试系统维护一个测试计数器。您要么将要运行的测试数量放在程序的顶部，要么声明您不会跟踪它。这可以防止您的测试过早退出，但是还有其他保护措施，所以它并不是那么重要。
每隔一段时间，就会有人尝试编写一个程序来为您计算测试次数。当然，这被一个简单的循环打败了。无论如何，他们都会继续前进，做越来越复杂的技巧来尝试检测循环并猜测会有多少次迭代并解决停机问题。通常他们宣称它必须“足够好”。
于 2008-10-25T08:22:33.847 回答
1
我曾经在 ATM（自动柜员机）领域从事一个集成项目。客户要求我从我的系统生成一个报告，以报告我的系统未收到国家交换机发送的交易！！
于 2008-11-26T08:36:07.670 回答
1
我找到了伯克利的一篇论文：Looper: Lightweight Detection of Infinite Loops at Runtime http://www.eecs.berkeley.edu/~jburnim/pubs/BurnimJalbertStergiouSen-ASE09.pdf
LOOPER 可能很有用，因为大多数无限循环都是微不足道的错误。然而，这篇论文甚至没有提到停机问题！
他们对自己的局限性有何看法？
[LOOPER] 通常无法推断循环，其中非终止取决于每次循环迭代中堆突变的细节。这是因为我们的符号执行在具体化指针方面是保守的，而且我们的符号推理不够强大。我们相信将我们的技术与形状分析和更强大的不变量生成和证明相结合将是有价值的未来工作。
换句话说，“问题将在下一个版本中修复”。
于 2012-09-16T16:14:12.047 回答
0
Eclipse 可视化编辑器 (VE) 可用于打开任何.java 文件。然后它解析 Java 源代码以寻找可视 bean。...
一些可视化编辑工具将仅提供该特定可视化工具本身生成的代码的可视化模型。后续直接编辑源代码会阻止可视化工具解析代码和构建模型。
然而，Eclipse VE ... 可以用于从头开始编辑 GUI，也可以用于从“硬编码”或内置于不同可视化工具中的 Java 文件。源文件可以使用图形查看器、JavaBeans 树或属性视图进行更新，也可以由源代码编辑器直接编辑。
也许我现在应该坚持使用马蒂斯。
无关，这里有人要求Eclipse 中的停止问题。
公平地说，VE 的领域非常有限，它可能不会因为反射等棘手的事情而疯狂。尽管如此，从任何java 文件中构建 GUI 的说法似乎都停止了。
于 2010-09-18T03:15:18.567 回答
-4
“您如何向我保证您的代码 100% 没有错误？”
于 2008-12-04T10:59:52.917 回答