Re: [請益] 那些語言或程式用上 多核心 CPU
※ 引述《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
推
05/20 17:23, , 1F
05/20 17:23, 1F
討論串 (同標題文章)