作者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