作者xcycl (XOO)
看板Programming
标题Re: [请益] 那些语言或程式用上 多核心 CPU
时间Mon May 21 22:19:17 2007
※ 引述《[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