作者ggg12345 (ggg)
看板Programming
标题Re: [请益] 那些语言或程式用上 多核心 CPU
时间Mon May 28 12:47:51 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;
: }
========================
Halting Problem 的证明通常都假设如果有这样的程式(或 Machine)
存在, 就可据此做个反例(反命题), 然後再让他对付自己(否逆命题),
最後证明不可能, 连带的原命题也就不可能.
若对此有兴趣, 那还是接 xen VM 会好玩一些, 因为 VM 可以使用
recursive VM , 就是把原 VM 整个程式当 input 喂给 VM 自己去跑,
看能否也一样正常的模拟起来 ? 状况非常像这个证明(其实不一样, 只
有把自己当 input 喂给自己).
是否存在一个程式可以判定所有的程式会不会停下来(Halt) ?
是否存在一个程式可以模拟所有的程式所要展现的特性 ?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.1.146