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

No.56897894 - 无标题 - 科学


回应模式
No.56897894
名 称
E-mail
标题
颜文字
正文
附加图片
•涵盖各类科学的讨论板块
•可盖棺定论各热门事件/关注后续/谣言粉碎
•干货什么的最喜欢了!
•请注意发言所包含的信息量,信息量过低的内容将移回综一
•引用请注明出处,民科、伪科学退散

无标题 无名氏 2023-04-18(二)09:55:44 ID:KfljGLa [举报] [订阅] [只看PO] 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”所以停机。不同的输入得到不同的结果,很正常啊,哪里有矛盾?
哪位肥哥疏导一下,毕竟书是划时代的大佬写的,应该是我脑子短路哪里理解错了(つд⊂)
Tips 无名氏 2099-01-01 00:00:01 ID:Tips超级公民 [举报] No.9999999 管理
( `д´)就不能学学动画版的萌豚,多看看动画片
无标题 无名氏 2023-04-18(二)12:37:10 ID:OQ4nsmr [举报] No.56900985 管理
我强烈怀疑是你看岔了原表述,请上原文
收起 查看大图 向左旋转 向右旋转
无标题 无名氏 2023-04-18(二)12:41:58 ID:nUUXMhV [举报] No.56901092 管理
来点不保真的维基百科
无标题 无名氏 2023-04-18(二)13:02:24 ID:P7D4rsT [举报] No.56901441 管理
没记错的话按照图灵机的定义,程序等待输入的话好像意味着它还没开始运行吧,自然谈不上停机与否了( ゚∀。)
无标题 无名氏 2023-04-18(二)13:13:52 ID:vFQljvo [举报] No.56901660 管理
你的表述不太一样
停机问题可以说是
问是否存在程序f(x)对于输入的一段程序x
如果x死循环输出0 如果x正常结束输出1

解决方式是利用f(x)构建g(x())
对于输入的一个有输入的程序x()
如果x(x)死循环输出1 正常结束输出死循环
如此
则g(g())的输出无法判断
因此f(x)不存在
无标题 无名氏 2023-04-18(二)13:16:41 ID:vFQljvo [举报] No.56901721 管理
和我们做程序的人工输入不一样
停机问题中的“程序”“输入”更加类似于各种C语言教程中“函数”“参数”,是不存在“等待输入”的
收起 查看大图 向左旋转 向右旋转
无标题 无名氏 2023-04-18(二)13:21:07 ID:cQPjPPS [举报] No.56901816 管理
上学期刚学过
无标题 无名氏 2023-04-18(二)15:24:31 ID:Hm74GiO [举报] No.56903771 管理
讨论未受精的卵是否活着是没意义的
收起 查看大图 向左旋转 向右旋转
无标题 无名氏 2023-04-18(二)17:04:21 ID:ocQbD6C [举报] No.56906312 管理
分享图片
无标题 无名氏 2023-04-18(二)18:07:24 ID:vFQljvo [举报] No.56907664 管理
我再整理一下
你的书上可能记录得有问题。
停机问题是
问是否存在程序f(x)对于任何一段程序x
如果x死循环输出0 如果x正常结束输出1


假设f(x)存在
则可以构建g(x()),这个程序可以输入x(),x()是一个有输入的程序

g(x())的伪代码:
1 运行f(x(x()))
2 如果值为0为输出1 否则进入死循环

如此
我们判断一下
g(g())是否可以结束:

如果g(g())可以结束
即源程序第一行f(g(g())输出了0
即g(g())无法结束

如果g(g())无法结束
即源程序第一行f(g(g())输出了1
即g(g())可以结束

因此f(x)不存在
无标题 无名氏 2023-04-18(二)19:30:49 ID:bhrYud5 [举报] No.56909445 管理
不能把程序x看成一个个输入和输出组成的键值对本身,而应该把x看作输入与输出的关系(集合论意义上的)。

因此f(x)不应该是判断对于某个输入x是否会停机,而是是否对所有输入,x都能停机。

具体地类比,x可以当成函数,而f是泛函(而不是函数)
收起 查看大图 向左旋转 向右旋转
无标题 无名氏 2023-04-20(四)17:39:01 ID:BzHFIfd [举报] No.56950554 管理
分享图片
无标题 无名氏 2023-04-20(四)17:41:01 ID:BzHFIfd [举报] No.56950585 管理
“等待输入”就涉及到实无穷是否可能了,总之不推荐这么想
无标题 无名氏 2023-04-20(四)18:02:34 ID:22b93o1 [举报] No.56950945 管理
不要用“程序”这么宽泛的术语,停机问题作用于图灵机,请用图灵机来理解
收起 查看大图 向左旋转 向右旋转
无标题 无名氏 2023-04-27(四)17:32:12 ID:BzHFIfd [举报] No.57092327 管理
分享图片

UP主: