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