Halting Problem的讨论

有关于Halting Problem的一点点讨论

Halting Problem with no input:

Halting Problem with no input:

Show that given a Turing Machine MMM, there is no algorithm to determine whether MMM halts when the input to the machine is a blank tape.

以下回答搬运自网络 Click here to see the original

现在假如我拥有了一个程序，可以用来判断另一个程序是会终止，还是不断的陷入死循环，那么我最终的代码八成会长成这样：

def judge_halt(*Program, *inputs):if (something extremely clever):return Trueelse:return False

这里的 “something extremely clever”就是一个用于判断程序是否会终止的代码串，我们暂且不去管它是个啥。

然后呢？学计算机的往往喜欢套娃，我们也来套一套娃：

if __name__ == "__main__":print(judge_halt(*judge_halt))

这个套娃好像没什么威力，我们整一整其他的活，比如说自己搞一个循环不断的代码：

def stop_on_itself(*program):return judge_halt(*program, *program)def kick_your_ass(*program):if (stop_on_itself(*program)):while True:passreturn Falseelse:return True

这个小东西看起来不错的样子,我们再来套一套娃：

if __name__ == "__main__":print(kick_your_ass(*kick_your_ass))

好像奇怪的事情发生了，我们来仔细看一看这里将会发生的事情

如果 kick_your_ass(*kick_your_ass) 这一行代码陷入了死循环, 这意味着stop_on_itself(*kick_your_ass)判了真，但是stop_on_itself(*kick_your_ass)判真这件事情本身意味着什么呢？这意味着judge_halt(*kick_your_ass, *kick_your_ass)将会return一个True，也就是说kick_your_ass(*kick_your_ass)不会陷入死循环

矛盾了对吧？开始我们说kick_your_ass(*kick_your_ass)会陷入自循环来着。

从另一个方面来说，如果这个代码直接返回了一个True呢？应该也是有矛盾的。因为这意味着stop_on_itself(*kick_your_ass)应该返回一个False，也就是说judge_halt(*kick_your_ass, *kick_your_ass)这一行代码返回了一个False，也就是说kick_your_ass(*kick_your_ass))应该会不断的循环下去，这也就和之前程序直接跳出发生了矛盾。

非常漂亮的一个证明，这告诉我们无法存在一个程序来判断另一个成序是否将会跳出。

但是这并没有解决我们的问题，因为这里的问题当中问的是一个没有input的程序，也就是说不能够用上面这种套娃的形式来构造矛盾。但无论如何这样的讨论告诉我们什么道理呢？

有一些事情是没有答案的，就像你不能根据你手头代码的语法结构来判断它是否终止那样，你得用你手头一台很快很快的电脑亲自跑一跑。而如果电脑一时半会儿跑不出来呢？你得亲自看看你手头的代码是什么意思。尝试着理解它，知道其中的矛盾，然后决定让电脑这样一直跑下去——消耗着电能地继续这样跑下去——到底有没有意义。

像极了人生qwq