※ 引述《[email protected] (小強)》之銘言： : ※ 引述《[email protected] (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