※ 引述《DreamLinuxer ( )》之铭言： : ※ 引述《xcycl (XOO)》之铭言： : : 如果程式 N 不会停的话，判断程式 M 也跟着不停住，那其实也对。 : : 像是在 Unix 下 time 指令，不就会丢给你程式 M 的执行时间呢 XD : : 当然"判断多少花多少时间"，绝对是 undecidable 的， : : 我只是想说，问题是 undecidable 不代表写不出程式啊 ... : 一个问题是undecidable就是说不存在程式可以decide这个问题 : 既然不存在到底是要怎麽写? ==================================================================== 粗略的说 Halting Problem , 就是说不存在一种算法或程式, 可以针对所有的 程式, 透过计算判断, 判定最终是否会停还是不会停. 没有这种如此本事高强的程式或算法, 并不表示本事差一点的算法或程式就不 存在, 辟如一个程式都没 if loop , 开始到结束只有算术计算的 assignment statement(除了分母=0 例外) , 那是能判断计算时间也能知道何时会结束的. 就像 compiler 不会知道程式解题解对了没有, 但 Compiler 知道语法写错是 翻译不出对的指令, 但也能替你的程式做些假设的状况强行翻译, 看起来好像 真的能自动除错, 但也不保证就猜对. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.115.5.62