什麼是圖靈機正在停擺？

Question

我是新的可判定性。我讀過停止問題，但沒有得到任何實際上暗示的東西。我已經搞砸了解釋。

任何人都可以提供我任何聲音的解釋或至少一些細節，這將有很大的幫助？

Answer 1

您可以將圖靈機想象成一種可以執行程序的理論計算機。圖靈機的程序由一組狀態和這些狀態之間的轉換組成。運行在圖靈機上的程序可以訪問一個叫做磁帶的輸入源，它有一些可以處理程序的字符串（可能是空的）。圖靈機的所有程序要麼是return true（halt-accept），要麼是return false（停止拒絕），要麼根本沒有return任何東西 - while (true) ; return true;。根據您的定義，機器可能也會有throw的異常（崩潰）;但通常崩潰被認爲是像try { /*crash*/ } catch (Exception) { return false; }這樣的崩潰意味着停止拒絕。

停機問題，那麼，是是否可以編寫一個程序對於一個圖靈機，其輸入爲圖靈機另一程序和輸入的一些字符串，它返回true或false（停止-接受或停止，拒絕）如果程序已經停止了提供的輸入並返回false否則（即，如果程序永不停止）。

事實證明，答案是沒有這樣的通用程序存在於圖靈機上。假設一個確實存在，M。給定輸入m和i它接受如果m在i停止並且否則拒絕。我們可以專門用來愚弄M另一個程序：

N(i) 
1. if M(N, i) then loop forever; 
2. otherwise return true 

現在是否繼續工作M上N：

1. 假設M說，在輸入iN暫停。然後N將永久循環，並且M將會出錯。

2. 假設M說N永遠循環輸入i。那麼N將返回true和halt，因此M將會出錯。

在這兩種情況下，M想出了錯誤的答案對於我們N，因爲我們在關於M比它的存在並解決停機問題，其他任何假設，我們不難得出結論，沒有任何機器可以解決存在暫停問題。

（M如果不希望直接引用M，則可以將其作爲輸入傳遞給程序N作爲輸入）。