證明此語言是不可判定的

Question

以下語言L不可判定？

大號 = {中號 | 中號是圖靈機的描述和存在一個輸入長度的Xķ使得中號暫停後至多ķ步}

我認爲這是但我不能證明給我看。我試圖想到從停止問題中減少。

Answer 1

評論：暫停問題的一個實例詢問車牀否暫停輸入和。已知問題是不可判定的（但是半可判定的）。

您的語言L的確是不可判定的。這可以通過減少停機問題到大號顯示：

1. 對於停機問題實例（Ñ，ÿ），創建新的機器中號爲大號問題。
2. 在輸入X，中號會模擬（Ñ，ÿ）爲長度（X）步驟。
3. 如果仿真在該步驟內暫停，則暫停M。否則，M故意進入無限循環。因爲

這種減少是有效的：

• 如果（Ñ，ÿ）不最終在ķ步驟停止，然後中號將停止爲長度k的所有輸入或更大，因此M在L。
• 否則（Ñ，ÿ）不停止，然後中號不會暫停任何輸入字符串不管它有多長，從而中號不在大號。

最後，暫停問題是不可判定的，因此L是不可判定的。