※ 引述《somi (SoMiMi FaReRe)》之铭言： : ※ 引述《[email protected] (@++@)》之铭言： : : 不对吧 : : halting problem是"无法判断会不会`停'" : : 跟要花多少时间没关系 : : 教科书上有明确的定义喔 : : wikipedia也查的到 : 判断程式花多少时间 这个问题基本上比 Halting Problem还要困难 : 正式上来说 Halting Problem可被 reduce to (判断程式花多少时间). : 因此如果compiler可以判断程式要花多少时间 就等於解了halting problem. : 但已知 Halting Problem在Turing Machine上是undecidable : 所以(判断程式花多少时间)也是 undecidable. 如果程式 N 不会停的话，判断程式 M 也跟着不停住，那其实也对。 像是在 Unix 下 time 指令，不就会丢给你程式 M 的执行时间呢 XD 当然"判断多少花多少时间"，绝对是 undecidable 的， 我只是想说，问题是 undecidable 不代表写不出程式啊 ... --

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