（翻译）《黑客》2010年07月之“寻找死循环”的程序

来源：百度文库 编辑：神马文学网 时间：2024/10/04 15:43:08

“寻找死循环”的程序

译者：edward9145（注：希望有文采的朋友能帮忙翻译个好点的题目）

中英对照：http://article.yeeyan.org/compare/169370/131225

 

停机问题无解的一个证明

编辑原文　　不存在通用的检查代码漏洞的程序。这里，我不仅仅要下断言，我还会展示那会导致什么：我将证明即使你或许工作到筋疲力尽，你也不清楚计算是否会终止。
　　假设我们有一个名称为P的程序，该程序针对具体的输入的代码，能够让你知道，这段具体的源代码，和它所有的故障一起，最终是否会停止运行。
　　你开始调试你的代码，给一些适当的数据，同时P开始工作，而一小会儿后（在有限的计算时间）P正确地推断出该程序是否出现了无限循环。
　　如果没有死循环，那么P打印出"Good"。这意味着在此的输入作业将停止，因为它应该停下。但如果它检测到一个不可停止的循环，那么P报告"Bad"！ ---而这意味着你遇到麻烦了。
　　嗯，事实上，P不可能办到。因为如果你写了这段代码，并把它交给我，我可以用它来建立一个逻辑约束，那将彻底推翻你的理由并改变你的想法。
　　这是我将使用的技巧——并且它做起来很简单。我将定义一个程序，称之为Q。Q将使用P的停机预测来引发一场糟糕的逻辑混乱。
　　对于一个具体的程序，比方说A，作为P的输入来源。A的第一步是调用Q，而Q被设计成从P处获取正确的描述——即A运行A自身时的循环行为。
　　运行时，如果P的回答是"Bad"，Q将突然停止。否则，Q将返回到顶部，并再次开始，不断地循环回来，直到宇宙死亡然后冻结陷入黑暗。
　　而“程序A调用Q”这段代码不会被搁置不用；我想让它来预测其本身的运行。当读取它自己的源代码，只是要怎么做呢？Q运行Q自身时的循环行为又是什么？
　　如果P警告有无限循环，Q将退出；然而P应该说出Q的真相！如果Q真的的要退出，那么P应该说"Good"---这使得Q开始循环（P会否认它。）
　　不管P怎样执行输出，Q将都将推翻它：Q使用了P的输出，这使P看起来很愚蠢。无论P输出什么，它都无法预测Q：P错的时候是对的，真的时候是假的！
　　我迅速创建了一个悖论，简单地使用了你所假定的P。当你在设定P时，你就走进了一个圈套；你的假设，致使你刚好进入我所暗示的地方。
　　那么，这番论证可能得出的结果是什么呢？我无须告诉你；我敢确信你肯定知道。通过反证法，不存在一个程序，能像传说中的P一样运行。
　　你永远不可能找到预测计算机的行为的一般机械手段。这是件做不到事情。因此，我们程序员必须自己找到自己的程序漏洞。我们的电脑是失败者！
本文系Linux中国原创文章，版权归作者(edward9145)及Linux中国所有。
欢迎转载，请尽量保留本版权信息及原文出处。
原文：http://linux.cn/home/space-6718-do-thread-id-4862.html
（翻译）《黑客》2010年07月之“寻找死循环”的程序 （翻译）《黑客》2010年08月第三期之理解和应用操作转换(一) （翻译）《黑客》2010年08月第三期之理解和应用操作转换(二) 对死循环的解释 经典的死循环笑话 一个死循环的笑话 经典（转） 死循环 PDCA循环--工作程序 2010年2月15日黑客免费送QQ Taglib原理和实现之循环的Tag JSP 关键词:Taglib原理,实现之循环,Tag... 月 死鱼的冷眼 最详细的黑客教程_天空的月 带放奖 彩金循环程序使用说明2 我给毛主席当翻译的日子（之四） 10月10日寻找美食之烤全羊总结 郭之纯：王贝之死折射四种病态风尚2010年12月01日 08:15青年时报 共有评论61条 关于批处理的学习之四[条件 循环]_ 爆笑！一个死循环的笑话——看完绝对晕！ 自定义你的启动程序(更新至2008年11月27日) 2010年9月11日黑客送最新免费QQ号 55face - QQ资源版 - Face学园 ... 最简练的招数寻找无限上涨牛股-09年3月***** 枫月黑客记事本(只为想学黑客的人倾力分享)V1.1 beta 绿色中文免费版 揭秘不可按套路翻译的英语句子http://www.sina.com.cn 2010年02月22日 09:52 沪江英语 VC知识库BLOG-Panic的小屋-[翻译]程序风格的要素－C 风格指南