Talk:停机问题

维基百科,自由的百科全书
跳到导航 跳到搜索
数学专题 (获评高重要度)
Nuvola apps edu mathematics-p.svg 本條目属于数学专题范畴,该专题旨在改善中文维基百科数学类内容。如果您有意参与,请浏览专题主页、参与讨论,并完成相应的开放性任务。
 未知级未评  根据专题质量评级标准,本條目尚未接受评级
   根据专题重要度评级标准,本條目已评为高重要度
电脑和信息技术专题 (获评极高重要度)
LampFlowchart.svg 本條目属于电脑和信息技术专题范畴,该专题旨在改善中文维基百科資訊科技相关条目类内容。如果您有意参与,请浏览专题主页、参与讨论,并完成相应的开放性任务。
 未知级未评  根据质量评级标准,本條目尚未接受评级
 极高  根据重要度评级标准,本條目已评为极高重要度

Untitled[编辑]

不理解对停机问题的证明:

设停机问题有解,即:存在过程H(P, I)可以给出程序P在输入I的情况下是否可停机。假设若P在输入I时可停机,H输出“停机”,反之输出“死循环”,

这个假设有无问题。既是死循环,就说明在一直不停地在计算而没有得到结果,这时怎么让其判定自己是死循环而输出死循环结束自己呢? --Aabbcc001 2007年9月22日 (六) 14:26 (UTC)

  • 他是假設存在一個圖靈機能夠決定此問題,那麼建構一個新圖靈機基於此圖靈機的輸出,當此圖靈機輸出否(無窮迴圈)則不改變行為,此圖靈機輸出是(停止)則執行無窮迴圈,也就是說此假設的圖靈機本身已經能夠在有限的時間中決定他的輸入是否會停......Arcanum (留言) 2008年7月10日 (四) 21:55 (UTC)

停机问题和参见里的未解决的数学问题本质上没什么联系吧。 --60.2.23.250 (留言) 2011年7月23日 (六) 11:14 (UTC)

第一段“在使用 oracle 输入的帮助下”似乎是笔误?

U(P) 的实现不符合定义啊(笑)[编辑]

原文定义如下:

int U(P) {
    if (H(P, P) == 1) {
        return 0;
    } else {
        while(1) { }
    }
}

燃鹅若进入死循环,返回值便不是 int 了啊……(笑)—以上未簽名的留言由Wang Nianyi對話貢獻)於2017年8月27日 (日) 13:27 (UTC)加入。

仅当返回的时候才返回 int,而进入死循环的时候便不会返回——这个实现是正确的。MS1337留言) 2017年11月13日 (一) 18:10 (UTC)