[1266] Halting Problem

Title Text:I found a counterexample to the claim that all things must someday die, but I don’t know how to show it to anyone.<

Origin:https://xkcd.com/1266/

https://www.explainxkcd.com/wiki/index.php/1266:_Halting_Problem

1936年,艾伦·图灵证明,算法不可能决定一个任意程序最终会停止,还是永远运行。后来被马丁戴维斯称为停机问题。该问题的官方定义是编写一个程序(实际上是图灵机),它接受程序及其参数作为参数。该程序需要在有限的时间内决定该程序是否会停止运行这些参数。

停止问题是计算机科学的基石问题。它主要用作证明给定任务是不可能的方法,通过显示解决该任务将允许人们解决停止问题。

然而,Randall提供了一种更简单的解决方案。他为“它停止了吗?”这个问题实现了自己的代码。它总是返回“真实”,并引导我们思考更大的图景。

从物理角度来看,根据我们目前对物理学的理解,这是对的。如果有足够的时间,任何程序都将停止。这是由于实际程序外部的因素。电力迟早会发出,或者包含该程序的记忆会被宇宙射线破坏,否则腐蚀会吞噬掉CPU中的硅,否则热力学第二定律会导致热量死亡。没有什么是永恒的,这包括一个正在运行的程序。

从数学的角度来看,情况并非如此:图灵机永远不会出现硬件故障,因为它不是物理机器。它是一个理论构造,它是数学定义的,独立于任何物理硬件。同样地,no?+鈪?+鈪?= 1,无论你在索赔上计算什么物理硬件。

对Randall代码的另一种解释是,无论何时调用其函数,括号中的程序实际上都在运行,这与某些编程结构一致。在这种情况下,函数将等到程序完成并退出,然后返回“True”。因此,Randall的功能在数学上是准确的。但它并没有解决问题,因为它只是将问题转移到函数本身是否会停止。

从实际的角度来看,程序员当然希望返回“假”,因为某些程序可以在数学上显示为永远运行。

标题文本进一步涉及到这个问题,声称找到了一个不需要死的东西的案例,但是Randall不知道如何向任何人展示它,因为事实上每个人都会死得更快而不是证明它会不死标题文本的措辞也可能是对费马最后定理的参考。

值得注意的是,兰德尔的解决方案,除了它的不健全性,解决的不仅仅是通常所说的形式的停顿问题。暂停问题需要两个参数(程序及其参数),而Randall的函数只接受一个(程序)。关于每个输入的程序是否停止的问题可以显示比停止问题更难解决,这意味着即使图灵机有一个额外的指令允许它检查程序是否停止给定参数,它仍然可以并不总是确认停止所有参数的给定程序是这样做的。

此漫画中的代码是用伪代码编写的,用于演示“算法”而不是某些现有编程语言中的实现。语法类似于C和Python的混合。

Leave a Reply

Your email address will not be published.

Categories