你什么时候遇到现场停止问题？ [关闭]
https://stackoverflow.com/questions/235984
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
你有什么时候亲自见过 停止问题 在该领域？这可能是当一个同事/老板提出一个违反计算基本限制的解决方案，或者当你意识到自己试图解决的问题实际上是无法解决的时候。
最近我提出它的时候是研究类型检查器。我们班级意识到编写一个完美的类型检查器是不可能的（一个可以接受所有运行没有类型错误的程序，并拒绝所有运行类型错误的程序），因为这实际上可以解决暂停问题。另一个是当我们在同一个类中意识到在类型检查阶段不可能确定除法是否会出现零，因为检查一个数字在运行时是否为零，也是暂停问题的一个版本。
解决方案
我字面上被分配了暂停问题，如“编写监视器插件以确定主机是否永久停机”。真的吗？好的，所以我只是给它一个门槛。 “不，因为它可能会在之后重新出现。”
随后进行了大量的理论阐述。
其他提示
多年前，我记得在一篇名为Basic Infinite Loop Finder或BILF的产品上阅读了一篇评论（在Byte杂志中，我相信）。 BILF应该扫描您的Microsoft Basic源代码并找到任何未终止的循环。它声称能够在代码中找到任何无限循环。
审稿人非常精明地指出，要使该计划在所有情况下都能运作，它必须解决暂停问题，并提供一个数学证明，说明为什么它不能在所有情况下都起作用。
在下一期中，他们发布了公司代表的一封信，解释说问题将在下一版本中修复。
更新：我在imgur上看到了这篇文章的图片。我记得错误的杂志。它是Creative Computing，而不是Byte。否则，就像我记得它一样。
您可以在 imgur 上查看高分辨率版本。
我正在进行的项目在整个过程中都存在不可判定的问题。它是一个单元测试生成器，所以一般来说它试图完成的是回答问题“这个程序做什么”。这是一个停顿问题的例子。在开发过程中出现的另一个问题是“给予两个（测试）功能相同的”？或者甚至“这两个调用（断言）的顺序是否重要”？
这个项目的有趣之处在于，即使你无法在所有情况下回答这些问题，你可以找到解决问题的智能解决方案90％时间，这个领域实际上非常好。
其他尝试推理其他代码的工具，如优化编译器/解释器，静态代码分析工具，甚至是重构工具，都可能会遇到停机问题（因此不得不找到解决方法）。
示例1.我的报告中有多少页？
当我学习编程时，我玩了一个工具来打印出来自数据的漂亮报告。显然，我希望它非常灵活和强大，因此报告生成器将结束所有报告生成器。
报告定义最终变得如此灵活，以至于图灵完成了。它可以查看变量，在备选之间进行选择，使用循环来重复。
我定义了一个内置变量N，即报表实例中的页数，因此你可以放一个字符串，表示“n的页面n”。在每个页面上。我做了两次通过，第一次计算页面（在此期间N被设置为零），第二次用实际生成它们，使用从第一次通过获得的N.
有时第一遍会计算N，然后第二遍会生成不同数量的页面（因为现在非零N会改变报告所做的）。我试着迭代地做通过，直到N安定下来。然后我意识到这是没有希望的，因为如果它没有安定下来怎么办？
然后，这导致了一个问题，“我能否至少检测并警告用户，如果迭代永远不会确定其报告产生的页数的稳定值？”幸运的是，此时我对阅读图灵，哥德尔，可计算性等感兴趣，并建立了联系。多年以后，我注意到MS Access有时会打印“第6页”，这是一件非常了不起的事情。
示例2：C ++编译器
编译过程涉及扩展模板。模板定义可以从多个特化中选择（足以作为“cond”），并且它们也可以是递归的。所以这是一个图灵完整（纯函数）元系统，其中模板定义是语言，类型是值，编译器实际上是一个解释器。这是一次意外。
因此，无法检查任何给定的C ++程序，并说明编译器原则上是否可以通过成功编译程序来终止。
编译器供应商通过限制模板递归的堆栈深度来解决这个问题。您可以用g ++调整深度。
由于工厂已全面投产，顾问无法“实时”运行他的软件来测试他的调度算法。相反，他写了一个漂亮的图形模拟器。当我们看到虚拟托盘在他的屏幕轨道布局上移动时，我问“你怎么知道你是否有任何日程安排冲突？”
他的快速回答，“简单 - 模拟永远不会停止。”
复杂的静态代码分析可能会遇到暂停问题。
例如，如果Java虚拟机可以证明一段代码永远不会访问数组索引越界，那么它可以省略该检查并运行得更快。对于某些代码，这是可能的;随着它变得越来越复杂，它就成了停滞不前的问题。
对于GPU应用程序中的着色器，这仍然是个问题。如果着色器具有无限循环（或非常长的计算），驱动程序（在一段时间限制之后）是否应该停止它，杀死碎片，或者让它运行？对于游戏和其他商业用途，前者可能就是你想要的，但对于科学/ GPU计算，后者就是你想要的。更糟糕的是，某些版本的Windows假设由于图形驱动程序在一段时间内没有响应，它会杀死它，这会在GPU上进行计算时人为地限制计算能力。
应用程序没有API来控制驱动程序应该如何操作或设置超时等等，并且驱动程序无法判断着色器是否完成。
我不知道最近这种情况是否有所改善，但我想知道。
这个的另一个常见版本是“我们需要消除我们的多线程代码中的任何死锁”。从管理角度来看，这是一个非常合理的请求，但是为了防止在一般情况下发生死锁，您必须分析软件可以进入的每个可能的锁定状态，这并不奇怪，等同于暂停问题。 / p>
有办法部分“解决”通过在锁定之上施加另一层（如定义的获取顺序），在复杂系统中出现死锁，但这些方法并不总是适用。
为什么这等同于暂停问题：
想象一下你有两个锁，A和B，以及两个线程，X和Y.如果线程X有锁A，并且也想要锁B，并且线程Y有锁B并且也想要A，那么你就有一个死锁。
如果X和Y都同时访问A和B，那么确保永远不会进入错误状态的唯一方法是确定每个线程可以通过代码获取的所有可能路径，以及顺序在所有这些情况下，他们可以获得并保持锁定。然后确定两个线程是否可以以不同的顺序获取多个锁。
但是，确定每个线程可以通过代码获取的所有可能路径（在一般情况下）等同于暂停问题。
Perl的测试系统维护着一个测试计数器。您要么将要运行的测试数量放在程序的顶部，要么声明您不会跟踪它。这样可以防止你的测试过早退出，但是还有其他防守因此并不是那么重要。
每隔一段时间，有人会尝试编写一个程序来计算你的测试次数。当然，这是一个简单的循环。无论如何，他们都在前进，做更多更精细的技巧来尝试和检测循环并猜测将会有多少次迭代并解决暂停问题。通常他们声明它必须“足够好”。
我曾经在ATM（自动柜员机）领域开展一个集成项目。客户要求我从我的系统生成报告，以便国家交换机发送的交易没有被我的系统接收!!
我找到了伯克利的一篇论文： Looper：运行时无限循环的轻量级检测 http://www.eecs.berkeley.edu/~jburnim/pubs /BurnimJalbertStergiouSen-ASE09.pdf
LOOPER可能很有用，因为大多数无限循环都是微不足道的错误。但是，本文甚至没有提到暂停问题！
他们对自己的局限性有什么看法？
[LOOPER]通常无法推断非终止的循环 取决于每次循环迭代中堆变异的细节。 这是因为我们的象征性执行是保守的 具体化指针，我们的象征性推理不够充分 强大。 我们相信我们的技术与形状分析相结合 更强大的不变生成和证明将是有价值的 未来的工作。
换句话说，“问题将在下一个版本中修复”。
来自（Eclipse）Visual Editor的功能概述：
Eclipse Visual Editor（VE）可以 用于打开 任何 .java文件。然后呢 解析Java源代码 对于视觉豆。 ...
只有一些可视化编辑工具 提供代码的可视化模型 特定的视觉工具本身 产生。随后直接编辑 的源代码可以防止 解析代码的可视化工具 建立模型。
然而，Eclipse VE可以是...... 用于从头开始编辑GUI，或 来自Java文件 '硬编码'或内置于不同的 视觉工具。源文件可以 要么使用图形进行更新 查看器，JavaBeans树或属性 查看或可以直接编辑 源编辑器。
也许我现在应该坚持马蒂斯。
无关，这里有人要求 Eclipse中的暂停问题。
公平地说，VE的领域非常有限，它可能不会因为反思等棘手的事情而疯狂。尽管如此，声称用 任何 java文件构建GUI似乎已经停止了。
“你怎么能向我保证你的代码100％没有错误？”
