討論:停機問題

由MS1337在話題U(P) 的實現不符合定義啊(笑)上作出的最新留言:7 年前
基礎條目 停機問題屬於維基百科數學主題的基礎條目第五級。請勇於更新頁面以及改進條目。
          本條目屬於下列維基專題範疇:
數學專題 (獲評未評級高重要度
本條目屬於數學專題範疇,該專題旨在改善中文維基百科數學類內容。如果您有意參與,請瀏覽專題主頁、參與討論,並完成相應的開放性任務。
 未評級未評  根據專題品質評級標準,本條目尚未接受評級。
   根據專題重要度評級標準,本條目已評為高重要度
電腦和資訊科技專題 (獲評極高重要度
本條目屬於電腦和資訊科技專題範疇,該專題旨在改善中文維基百科資訊科技相關條目類內容。如果您有意參與,請瀏覽專題主頁、參與討論,並完成相應的開放性任務。
 未評級未評  根據專題品質評級標準,本條目尚未接受評級。
 極高  根據專題重要度評級標準,本條目已評為極高重要度

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)回覆

返回 "停机问题" 頁面。