【Hacker News搬运】Scooping the Loop Snooper（2000）

[hackernews]

Title: Scooping the Loop Snooper (2000)

Scooping the Loop Snooper（2000）

Text:

hn link

Url: http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html

这篇文章的标题是“Scooping the Loop Snooper — Geoffrey K. Pullum”，作者是来自爱丁堡大学哲学、心理学和语言科学学院的Geoffrey K. Pullum。文章提供了一个关于停机问题不可判定的证明。

文章首先假设存在一个程序P，它能够对给定的输入程序进行判断，判断该程序是否会无限循环。如果程序不会无限循环，P会输出“Good”，意味着程序会在有限的时间内停止运行。如果程序会无限循环，P会输出“Bad”，意味着程序会陷入无限循环。

然而，作者指出，这样的程序P是不可能存在的。他通过定义另一个程序Q来证明这一点。程序Q会根据P对特定程序A的判断来执行不同的行为。如果P判断A会无限循环，那么Q会停止运行。否则，Q会无限循环，直到宇宙终结。

接着，作者将程序Q应用于其自身，即让Q判断其自身运行的结果。这里出现了矛盾，因为如果P判断Q会无限循环，那么Q会停止；但如果P判断Q会停止，那么Q会开始无限循环。无论P如何判断，Q都能利用P的输出来证明P的错误。

因此，作者得出结论，不存在一个程序能够像P那样工作，即无法通过机械的方式来预测计算机器的行为。这意味着计算机用户必须自己寻找程序中的错误。

这个证明最初在2000年发表于《Mathematics Magazine》，后来经过修正和重新发表。作者感谢了多位学者，包括Philip Wadler、Larry Moss和Damiano Mazza，以及已故的Dr. Seuss和Alan Turing的工作。

文章的版权属于Geoffrey K. Pullum，允许非商业、教育用途的复制或分发，前提是作者得到通知，并包含上述的版权归属信息。

Post by: soferio

Comments:

dang: Related:<p><i>Scooping the Loop Snooper (2000)</i> - <a href="https://news.ycombinator.com/item?id=30783422">https://news.ycombinator.com/item?id=30783422</a> - March 2022 (31 comments)<p><i>Scooping the Loop Snooper: Proof That the Halting Problem Is Undecidable (2000)</i> - <a href="https://news.ycombinator.com/item?id=20956756">https://news.ycombinator.com/item?id=20956756</a> - Sept 2019 (33 comments)<p><i>Scooping the Loop Snooper (2000)</i> - <a href="https://news.ycombinator.com/item?id=10077471">https://news.ycombinator.com/item?id=10077471</a> - Aug 2015 (2 comments)

dang: 相关：<p><i>Scooping the Loop Snooper（2000）</i>-<a href=“https://；&#x2F；news.ycombinator.com&#x2F！item？id=30783422”>https://&#x2F；news.ycombinator.com&#x2F；项目id=30783422</a>-2022年3月（31条评论&#x2F；news.ycombinator.com&#x2F；项目id=20956756</a>-2019年9月（33条评论）<p><i>抓取循环嗅探器（2000）</i>-<a href=“https://F；&#x2F；news.ycombinator.com/x2F；item？id=10077471”>https://&#x2F；news.ycombinator.com&#x2F；项目id=10077471</a>-2015年8月（2条评论）

skulk: Diagonalizations are some of the easiest to understand, yet most profound proofs in math. Another example is the proof that any continuum is larger in cardinality than the set of integers.<p><a href="https://en.m.wikipedia.org/wiki/Diagonal_argument" rel="nofollow">https://en.m.wikipedia.org/wiki/Diagonal_argument</a>

skulk: 对角化是数学中最容易理解但最深刻的证明之一。另一个例子是证明任何连续体的基数都大于整数集<p> <a href=“https://；&#x2F；en.m.wikipedia.org&#x2F！wiki&#x2F：Diagonal_argument”rel=“nofollow”>https://&#x2F；en.m.wikipedia.org&#x2F；wiki&#x2F；对角线_参数</a>

beders: Sweet poem. I remember being blown away when I studied computer science.
The whole idea that there are inherit limits to computing on Turing machines seemed crazy.<p>Gödel's incompleteness theorems has a similar proof that will mess with your brain

beders: 甜美的诗。我记得当我学习计算机科学时，我被震撼了。在图灵机上计算存在继承限制的整个想法似乎很疯狂<p> 哥德尔；的不完全性定理有一个类似的证明，会扰乱你的大脑：）

QuinnyPig: The halting problem--a tough endeavor<p>"Will the loop complete or run forever?"<p>Many fixes were attempted<p>(Lambda's 15 minute limit doesn't get exempted)<p>You'll quickly find there is no winning<p>As the LOADING ball keeps spinning<p>To date there remains a single hack:<p>Rip the cable out the back<p>You'll have an answer clarified:<p>"The loop is done; the power died."

QuinnyPig: 停顿的问题——一个艰难的努力<p>&quot；循环会完成还是永远运行&quot<p> 尝试了许多修复<p>（Lambda的15分钟限制没有得到豁免）<p>You；我很快就会发现没有获胜<p>因为LOADING球一直在旋转<p>到目前为止，还有一个破解：<p>把电缆从后面撕开<p>你；我要澄清一个答案：；循环完成；力量消失了&quot；

g___: Suppose O is the oracle for the halting problem.<p>We create a machine: given a program P, ask O whether P halts given input P and negate the answer.<p>λP. ~O (P P)<p>Now we ask whether this machine will halt given its own source code as input. In symbols:<p>(λP. ~O (P P)) (λP. ~O (P P))<p>which is the Y-combinator in lambda calculus.

g___: 假设O是解决停顿问题的预言家<p> 我们创建一个机器：给定一个程序p，问O p是否停止给定的输入p并否定答案<p> λp~O（P P）＜P＞现在我们问，如果输入了它自己的源代码，这台机器是否会停止。在符号中：<p>（λp.~O（p p））（λp.~ O（p））<p>它是lambda演算中的Y组合子。