推 rightson:但halting problem和時間是扯不上關係的 140.113.239.71 05/15 17:20
推 rightson:個人認為原po邏輯跳太多 扯太遠 140.113.239.71 05/15 17:23
→ rightson:但 他電了之前那個亂問的人 還不錯 140.113.239.71 05/15 17:26
※ 引述《[email protected] (@++@)》之銘言：
: 不對吧
: halting problem是"無法判斷會不會`停'"
: 跟要花多少時間沒關係
: 教科書上有明確的定義喔
: wikipedia也查的到
判斷程式花多少時間 這個問題基本上比 Halting Problem還要困難
正式上來說 Halting Problem可被 reduce to (判斷程式花多少時間).
因此如果compiler可以判斷程式要花多少時間 就等於解了halting problem.
但已知 Halting Problem在Turing Machine上是undecidable
所以(判斷程式花多少時間)也是 undecidable.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 132.239.55.127