Tips无名氏No.9999999

2099-01-01 00:00:01 ID: Tips

(;´Д`)医生！你说话啊！

无标题无名氏No.56900985

2023-04-18(二)12:37:10 ID: OQ4nsmr

我强烈怀疑是你看岔了原表述，请上原文

无标题无名氏No.56901092

2023-04-18(二)12:41:58 ID: nUUXMhV

来点不保真的维基百科

无标题无名氏No.56901441

2023-04-18(二)13:02:24 ID: P7D4rsT

没记错的话按照图灵机的定义，程序等待输入的话好像意味着它还没开始运行吧，自然谈不上停机与否了( ﾟ∀。)

无标题无名氏No.56901660

2023-04-18(二)13:13:52 ID: vFQljvo

你的表述不太一样
停机问题可以说是
问是否存在程序f（x）对于输入的一段程序x
如果x死循环输出0 如果x正常结束输出1

解决方式是利用f（x）构建g（x（））
对于输入的一个有输入的程序x（）
如果x（x）死循环输出1 正常结束输出死循环
如此
则g（g（））的输出无法判断
因此f（x）不存在

无标题无名氏No.56901721

2023-04-18(二)13:16:41 ID: vFQljvo

和我们做程序的人工输入不一样
停机问题中的“程序”“输入”更加类似于各种C语言教程中“函数”“参数”，是不存在“等待输入”的

无标题无名氏No.56901816

2023-04-18(二)13:21:07 ID: cQPjPPS

上学期刚学过

无标题无名氏No.56903771

2023-04-18(二)15:24:31 ID: Hm74GiO

讨论未受精的卵是否活着是没意义的

无标题无名氏No.56906312

2023-04-18(二)17:04:21 ID: ocQbD6C

分享图片

无标题无名氏No.56907664

2023-04-18(二)18:07:24 ID: vFQljvo

我再整理一下
你的书上可能记录得有问题。
停机问题是
问是否存在程序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）不存在