作者somi (SoMiMi FaReRe)
看板Programming
标题Re: [请益] 那些语言或程式用上 多核心 CPU
时间Tue May 15 16:00:16 2007
※ 引述《[email protected] (@++@)》之铭言：
: 不对吧
: halting problem是"无法判断会不会`停'"
: 跟要花多少时间没关系
: 教科书上有明确的定义喔
: wikipedia也查的到
判断程式花多少时间 这个问题基本上比 Halting Problem还要困难
正式上来说 Halting Problem可被 reduce to (判断程式花多少时间).
因此如果compiler可以判断程式要花多少时间 就等於解了halting problem.
但已知 Halting Problem在Turing Machine上是undecidable
所以(判断程式花多少时间)也是 undecidable.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 132.239.55.127
1F：推 rightson:但halting problem和时间是扯不上关系的 140.113.239.71 05/15 17:20
2F：推 rightson:个人认为原po逻辑跳太多 扯太远 140.113.239.71 05/15 17:23
3F：→ rightson:但 他电了之前那个乱问的人 还不错 140.113.239.71 05/15 17:26