Re: [請益] 那些語言或程式用上 多核心 CPU
※ 引述《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
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 25 之 30 篇):