请教一下抽象数学/逻辑学的停机问题。
书上这么写的:记一程序为x,这个程序要么在有限步内结束,即“停机”,要么哪里产生死循环后永久运行,即“不停机”。问:是否存在程序F,把任意程序x输进去,输入的操作记为F(x),F判定x会不会停机,如果x不停机则F停机。
书上的答案:不存在。考虑把F输入到F里,即F(F),如果里面F不停机,则外面F停机,这样F又停机又不停机,矛盾,所以不存在这样的F。
我觉得书上的论证是错的,理由是
1.如果“等待输入”不视为“不停机”的一种,那么:里面F等输入,所以整个F(F)也等输入,F(F)不是个完整的程序,必须输入变成F(F(x))才能跑,讨论它停机与否没有意义。
2.如果“等待输入”视为“不停机”的一种,那么:里面F等输入不停机,所以外面F判定停机。里面F没有输入所以不停机,外面F的输入是“没有输入的F”所以停机。不同的输入得到不同的结果,很正常啊,哪里有矛盾?
哪位肥哥疏导一下,毕竟书是划时代的大佬写的,应该是我脑子短路哪里理解错了(つд⊂)