No.56897894 - 科学
无标题无名氏No.56897894 只看PO
2023-04-18(二)09:55:44 ID:KfljGLa
请教一下抽象数学/逻辑学的停机问题。
书上这么写的：记一程序为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”所以停机。不同的输入得到不同的结果，很正常啊，哪里有矛盾？
哪位肥哥疏导一下，毕竟书是划时代的大佬写的，应该是我脑子短路哪里理解错了(つд⊂)
