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

看板Programming作者 (XOO)時間18年前 (2007/05/21 14:19), 編輯推噓0(000)
留言0則, 0人參與, 最新討論串25/30 (看更多)
※ 引述《hellfire.bbs@bbs.cs.nctu.edu.tw (小強)》之銘言: : ※ 引述《xcycl.bbs@ptt.cc (XOO)》之銘言: : > Well, 我講嚴謹一點, : > Turing-recognizable 是嚴格包含 Turing-decidable 語言的。 : > 而 language 是 recogizable 但不是 decidable 的, : > 意指存在 Turing Machine 能夠 recognize 這問題,只是不見得 : > 任意的 input 一定會 halt。講成白話,意思就是程式寫得出來, : > 只是不見得會停而已。 : > 所以能不能 decide 跟寫不寫得出程式無關。 : 好吧 : 那請您告訴我這個簡單的procedure到底會不會停? : 在下資質駑鈍真的想不出來 : while (true) { : int x = get random number from 0 to 100000 : if (x == 10) break; : } 必須明確定義, 何謂 "get a random number" 一般程式語言內建的函式是 pseudo-random generator 並不是真正 "random", 當然,就如同之前有人回的,一般亂數產生器跑夠多次之後,會取到 10 而會停住。 n 若是一機率分配函數 p:{1, ..., 100000} → [0, 1], Σp(i) = 1 i=1 那就只是機率問題。但就算 p(10) 的機率不等於 0 , 也只能說該 procedure 是 almost surely 會停的,但不能"確定"會停, 畢竟每次都取不到 10 的情況是存在,只是機率為零。 你可以看看 Probabilistic Turing Machine 的理論, 在 Wikipedia 或 計算理論和計算複雜度的教本都會提到 PTM 的理論模型。 如果你想藉此來闡述 "不存在程式可以判斷,其他程式是否會停" 這個觀念, 那你必須說明清楚,判斷是指任一輸入都可以在有限步驟內給出答案,也就是 decide。 但是這並不代表 "不存在程式可以 recognize,其他程式是否會停"。 在這裡說的 recognize, decide 請麻煩參考教本的定義,不要望文生義。 最後,幫你複習一下機率:事件一定發生的話,機率一定是 1;反之不成立, 用測度的語言來說,該事件跟樣本空間相差一個測度為零的集合。 因此,當某事件機率為 1 時,稱該事件 almost surely (中文不知道怎麼翻的)會發生。 題外話,在當代機率論公設(Kolmogorov提出的)底下,無法實作出能夠機會均等地, 隨機取出任一整數的方法。 almost surely: http://en.wikipedia.org/wiki/Almost_surely PTM: http://en.wikipedia.org/wiki/Probabilistic_Turing_machine TM: http://en.wikipedia.org/wiki/Deterministic_Turing_machine -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.229.165.204
文章代碼(AID): #16KQfcnD (Programming)
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 25 之 30 篇):
文章代碼(AID): #16KQfcnD (Programming)