※ 引述《[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