作者DreamLinuxer ( )
看板Programming
标题Re: [请益] 那些语言或程式用上 多核心 CPU
时间Sun May 20 17:15:34 2007
※ 引述《xcycl (XOO)》之铭言：
: ※ 引述《somi (SoMiMi FaReRe)》之铭言：
: : 判断程式花多少时间 这个问题基本上比 Halting Problem还要困难
: : 正式上来说 Halting Problem可被 reduce to (判断程式花多少时间).
: : 因此如果compiler可以判断程式要花多少时间 就等於解了halting problem.
: : 但已知 Halting Problem在Turing Machine上是undecidable
: : 所以(判断程式花多少时间)也是 undecidable.
: 如果程式 N 不会停的话，判断程式 M 也跟着不停住，那其实也对。
: 像是在 Unix 下 time 指令，不就会丢给你程式 M 的执行时间呢 XD
: 当然"判断多少花多少时间"，绝对是 undecidable 的，
: 我只是想说，问题是 undecidable 不代表写不出程式啊 ...
一个问题是undecidable就是说不存在程式可以decide这个问题
既然不存在到底是要怎麽写?
--
如果真的写出这种程式一定得Turing Award
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.209.144
1F：推 buganini:他的意思应该是不可计算，但可测量140.113.122.162 05/20 17:23