你什么时候遇到现场停止问题？
Cla*_*diu 65 language-agnostic theory field turing-machines halting-problem
When have you ever personally come upon the halting problem in the field? This can be when a co-worker/boss suggested a solution which would violate the fundamental limits of computation, or when you realized yourself that a problem you were trying to solve was, in fact, impossible to solve.
我最近想出来的时候是研究类型检查器.我们班级意识到编写一个完美的类型检查器是不可能的(一个可以接受所有运行没有类型错误的程序,并拒绝所有运行类型错误的程序),因为这实际上可以解决暂停问题.另一个是当我们在同一个类中意识到在类型检查阶段不可能确定除法是否会出现零,因为检查一个数字在运行时是否为零,也是暂停问题的一个版本.
Kir*_*ser 58
我确实已经分配了暂停问题,如"编写监视器插件以确定主机是否永久停机".真的吗？好的,所以我只是给它一个门槛."不,因为它可能会在之后重新出现."
随后进行了大量的理论阐述.
- 这个问题实际上很容易在.NET中解决.只需添加对System.Future的引用,然后可以使用System.Future.Fact类中的一些静态方法.在你的情况下:if(System.Future.Fact.IsPermanent(委托检查服务器是否在这里)){...} (13认同)
- 哇 - 哇,哇.在那个人心中必须存在的不合逻辑的深度让我感到困惑...... (5认同)
- @Lasse如果我们谈论Python会更加可信:)(不是我不喜欢.NET,但你知道......`import antigravity`和所有......) (5认同)
- @muntoo你似乎在第2行有一些无法访问的代码 (5认同)
- @Erik不,*你*是不合逻辑的.该程序非常简单:`host.self_destruct(); 打印("永久向下.");`. (4认同)
Fer*_*cio 42
几年前,我记得曾经读过一篇名为Basic Infinite Loop Finder或BILF的评论(在Byte杂志中,我相信).BILF应该扫描您的Microsoft Basic源代码并找到任何未终止的循环.它声称能够在代码中找到任何无限循环.
审稿人非常精明地指出,要使该计划在所有情况下都能运作,它必须解决暂停问题,并提供一个数学证明,说明为什么它在所有情况下都无效.
在下一期中,他们发布了公司代表的一封信,解释说问题将在下一版本中修复.
更新:我在imgur上看到了这篇文章的图片.我记得错误的杂志.它是Creative Computing,而不是Byte.否则,就像我记得的那样.
- 这真可笑!某处有可用的副本吗？ (18认同)
- 这可能是在70年代末或80年代初期.当时网络并不那么受欢迎;-) (3认同)
- BILF公司什么时候停止营业？ (3认同)
Mic*_*ski 34
我正在进行的项目现在有着不可思议的问题.它是一个单元测试生成器,所以一般来说它试图完成的是回答"这个程序做什么"的问题.这是一个停顿问题的例子.开发过程中出现的另一个问题是"两个(测试)功能是否相同"？甚至"这两个电话(断言)的顺序是否重要"？
这个项目的有趣之处在于,即使你无法在所有情况下回答这些问题,你也可以找到能够在90%的时间内解决问题的智能解决方案,这对于这个领域来说实际上是非常好的.
尝试推理其他代码的其他工具,如优化编译器/解释器,静态代码分析工具,甚至是重构工具,都可能会遇到停机问题(因此被迫找到解决方法).
Dan*_*ker 28
示例1.我的报告中有多少页？
当我学习编程时,我玩了一个工具来打印出来自数据的漂亮报告.显然,我希望它非常灵活和强大,因此报告生成器将结束所有报告生成器.
报告定义最终变得如此灵活,以至于图灵完成了.它可以查看变量,在备选之间进行选择,使用循环来重复.
我定义了一个内置变量N,即报表实例中的页数,因此您可以在每个页面上放置一个表示"N页n"的字符串.我做了两次通过,第一次计算页面(在此期间N被设置为零),第二次用于实际生成它们,使用从第一遍获得的N.
有时第一遍会计算N,然后第二遍会生成不同数量的页面(因为现在非零N会改变报告所做的).我试着迭代地做通过,直到N安定下来.然后我意识到这是没有希望的,因为如果它没有安定下来呢？
这就引出了一个问题,"我是否至少可以检测并警告用户迭代是否永远无法确定其报告生成的页数的稳定值？" 幸运的是,此时我对阅读图灵,哥德尔,可计算性等感兴趣并建立了联系.
多年以后,我注意到MS Access有时会打印"第6页,共5页",这真是一件非常了不起的事情.
示例2:C++编译器
编译过程涉及扩展模板.模板定义可以从多个特化中选择(足以作为"cond"),它们也可以是递归的.所以这是一个图灵完整(纯函数)元系统,其中模板定义是语言,类型是值,编译器实际上是一个解释器.这是一次意外.
因此,无法检查任何给定的C++程序,并说明编译器原则上是否可以成功编译程序.
编译器供应商通过限制模板递归的堆栈深度来解决这个问题.您可以用g ++调整深度.
n8w*_*wrl 19
许多月前,我正协助我们公司的一名顾问,他们正在实施一个非常复杂的铁路系统,以便在1500度高炉内进出金属零件.赛道本身是一个相当复杂的"迷你railyard"在车间,在几个地方交叉.根据时间表,几个电动托盘可以将一筐零件穿过.炉门在尽可能短的时间内打开是非常重要的.
由于工厂已全面投产,顾问无法"实时"运行他的软件来测试他的调度算法.相反,他写了一个漂亮的图形模拟器.当我们看到虚拟托盘在他的屏幕轨道布局上移动时,我问"你怎么知道你是否有任何调度冲突？"
他的快速回答是"简单 - 模拟永远不会停止."
- meta部件是为什么直到高炉才能让我理解他的导轨系统不是Ruby Web应用程序. (6认同)
Jas*_*hen 13
复杂的静态代码分析可能会遇到停顿问题.
例如,如果Java虚拟机可以证明一段代码永远不会访问数组索引越界,那么它可以省略该检查并运行得更快.对于某些代码,这是可能的; 随着它变得越来越复杂,它就成了停滞不前的问题.
joe*_*eld 11
对于GPU应用程序中的着色器,这仍然是一个问题.如果着色器具有无限循环(或非常长的计算),驱动程序(在一段时间限制之后)是否应该停止它,杀死碎片,或者让它运行？对于游戏和其他商业用途,前者可能就是你想要的,但对于科学/ GPU计算,后者就是你想要的.更糟糕的是,某些版本的Windows假设由于图形驱动程序在一段时间内没有响应,它会杀死它,这会在GPU上进行计算时人为地限制计算能力.
应用程序没有API来控制驱动程序应该如何操作或设置超时等等,并且驱动程序无法判断着色器是否完成.
我不知道最近这种情况是否有所改善,但我想知道.
另一个常见的版本是"我们需要消除多线程代码中的任何死锁".从管理角度来看,这是一个非常合理的请求,但为了防止在一般情况下发生死锁,您必须分析软件可以进入的每个可能的锁定状态,这并不奇怪,等同于暂停问题.
有一些方法可以通过在锁定之上施加另一层(如定义的获取顺序)来部分"解决"复杂系统中的死锁,但这些方法并不总是适用.
为什么这相当于停止问题:
想象一下,你有两个锁,A和B,以及两个线程,X和Y.如果线程X有锁A,并且还想要锁B,并且线程Y有锁B并且也想要A,那么你有一个死锁.
如果X和Y都同时访问A和B,那么确保永远不会进入错误状态的唯一方法是确定每个线程可以通过代码获取的所有可能路径,以及它们的顺序可以在所有这些情况下获取并保持锁定.然后确定两个线程是否可以以不同的顺序获取多个锁.
但是,确定每个线程可以通过代码获取的所有可能路径(在一般情况下)等同于暂停问题.
Perl的测试系统维护着一个测试计数器.您要么将要运行的测试数量放在程序的顶部,要么声明您不会跟踪它.这样可以防止你的测试过早退出,但是还有其他防守因此并不是那么重要.
每隔一段时间,有人会尝试编写一个程序来计算你的测试次数.当然,这是一个简单的循环.无论如何,他们都在前进,做更多更精细的技巧来尝试和检测循环并猜测将会有多少次迭代并解决停止问题.通常他们声明它必须"足够好".
| 归档时间： |
|
| 查看次数： |
5206 次 |
| 最近记录： |