※ 引述《[email protected] (SoMiMi FaReRe)》之铭言： > ※ 引述《[email protected] (@++@)》之铭言： > : 不对吧 > : halting problem是"无法判断会不会`停'" > : 跟要花多少时间没关系 > : 教科书上有明确的定义喔 > : wikipedia也查的到 > 判断程式花多少时间 这个问题基本上比 Halting Problem还要困难 > 正式上来说 Halting Problem可被 reduce to (判断程式花多少时间). > 因此如果compiler可以判断程式要花多少时间 就等於解了halting problem. > 但已知 Halting Problem在Turing Machine上是undecidable > 所以(判断程式花多少时间)也是 undecidable. 感谢补充 其实原po没有讲"错" 只是叙述方式让我觉得他重新定义了halting problem ======= 这段非常怪，Compiler也许可以回答你每个指令要花多少周期做完，但无法回答你这程式 要花多少时间才能跑完，事实上，只要是图灵机（Turing Machine，目前的机器皆是）， 是无法回答这个问题的，因为这是所谓的Halting Problem. ^^ 用`是'这个字让我觉得这样讲有点问题 是我咬文嚼字太龟毛.. 让大家见笑了 -- ▄▄▄▄▄▄▄ ▄▄▄▄ ▄▄▄▄▄▄ ＜telnet://bbs.cs.nctu.edu.tw＞ █▄▄▄▄█ █ ▄▄▄▄▄█ Player: rightson ▄█▄▄▄▄█ ▄▄▄█ █▄▄▄▄▄ From: E071.Life.NCTU.edu.tw ☆ 次世代ＢＳ２ ☆ 可申请个人板 150MB 相簿 http://pic.bs2.to 交大资讯人 250MB