写作绅士,读作丧尸 X岛揭示板
顺猴者昌 逆猴者亡 首页版规 |用户系统 |移动客户端下载 | 丧尸路标 | | 常用图串及路标 | 请关注 公众号:【矛盾苇草】| 人,是会思考的芦苇
常用串:·豆知识·跑团板聊天室·公告汇总串·X岛路标

[只看PO]No.56897894 - 无标题 - 科学


•涵盖各类科学的讨论板块
•可盖棺定论各热门事件/关注后续/谣言粉碎
•干货什么的最喜欢了!
•请注意发言所包含的信息量,信息量过低的内容将移回综一
•引用请注明出处,民科、伪科学退散

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

UP主: