※ 引述《DreamLinuxer ( )》之銘言：
: ※ 引述《xcycl (XOO)》之銘言：
: : 如果程式 N 不會停的話，判斷程式 M 也跟著不停住，那其實也對。
: : 像是在 Unix 下 time 指令，不就會丟給你程式 M 的執行時間呢 XD
: : 當然"判斷多少花多少時間"，絕對是 undecidable 的，
: : 我只是想說，問題是 undecidable 不代表寫不出程式啊 ...
: 一個問題是undecidable就是說不存在程式可以decide這個問題
: 既然不存在到底是要怎麼寫?
Well, 我講嚴謹一點,
Turing-recognizable 是嚴格包含 Turing-decidable 語言的。
而 language 是 recogizable 但不是 decidable 的，
意指存在 Turing Machine 能夠 recognize 這問題，只是不見得
任意的 input 一定會 halt。講成白話，意思就是程式寫得出來，
只是不見得會停而已。
所以能不能 decide 跟寫不寫得出程式無關。
--
Sipser 寫的計算理論還滿淺顯的, 可以看一下搞清楚兩者的區別。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.142.221