圖靈機停機問題



輸入 - 一臺圖靈機和一個輸入字串 w

問題 - 圖靈機是否能在有限步驟內完成字串 w 的計算?答案必須是“是”或“否”。

證明 - 首先,我們假設存在這樣的圖靈機來解決這個問題,然後我們將證明它自相矛盾。我們將稱這個圖靈機為停機機,它在有限時間內產生“是”或“否”。如果停機機在有限時間內完成,則輸出為“是”,否則為“否”。以下是停機機的框圖:

Halting Machine

現在我們將設計一個反向停機機 (HM)’如下:

  • 如果 H 返回 YES,則無限迴圈。

  • 如果 H 返回 NO,則停止。

以下是“反向停機機”的框圖:

Inverted Halting Machine

此外,一個輸入為自身的機器 (HM)2 構建如下:

  • 如果 (HM)2 在輸入上停止,則無限迴圈。
  • 否則,停止。

在這裡,我們得到了一個矛盾。因此,停機問題是不可判定的

廣告