推 buganini:他的意思應該是不可計算，但可測量140.113.122.162 05/20 17:23
※ 引述《xcycl (XOO)》之銘言：
: ※ 引述《somi (SoMiMi FaReRe)》之銘言：
: : 判斷程式花多少時間 這個問題基本上比 Halting Problem還要困難
: : 正式上來說 Halting Problem可被 reduce to (判斷程式花多少時間).
: : 因此如果compiler可以判斷程式要花多少時間 就等於解了halting problem.
: : 但已知 Halting Problem在Turing Machine上是undecidable
: : 所以(判斷程式花多少時間)也是 undecidable.
: 如果程式 N 不會停的話，判斷程式 M 也跟著不停住，那其實也對。
: 像是在 Unix 下 time 指令，不就會丟給你程式 M 的執行時間呢 XD
: 當然"判斷多少花多少時間"，絕對是 undecidable 的，
: 我只是想說，問題是 undecidable 不代表寫不出程式啊 ...
一個問題是undecidable就是說不存在程式可以decide這個問題
既然不存在到底是要怎麼寫?
--
如果真的寫出這種程式一定得Turing Award
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.209.144