Re: [請益] 那些語言或程式用上 多核心 CPU

[xcycl (XOO)]

※ 引述《somi (SoMiMi FaReRe)》之銘言：
: ※ 引述《[e-mail] (@++@)》之銘言：
: : 不對吧
: : 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
推 rightson:XD