「haltingproblem」矛盾證明

Question

我最近碰到了停止問題的矛盾證明。 在證明中，我們必須爲圖靈機提供一份程序副本和一份輸入副本，以決定程序是否停止輸入。在矛盾中，爲什麼它必須作爲程序和輸入的程序？對不起，如果聽起來很混亂。我可以簡單地給機器提供程序和隨機輸入，並得出相同的結論。

有誰能告訴我爲什麼？有沒有我沒有想到的具體原因？

Answer 1

首先讓我回來證明自己。

HALT_TM是不可判定

假定任何機器具有描述其中採用一個字符串的形式。讓HALT_TM = {<M, w>| M is a TM and M halts on input w}和A_TM = {<M,w>| M is a TM and accepts w}。在這裏，我假設我們知道A_TM是不可判定的（證明可以通過對角化來實現，並且意識到由於比圖靈機有更多的語言，並且由於給定的TM只決定一種語言，所以有些語言未被確定）。

假設相反，HALT_TM是可判定的，這意味着我們處置該語言的決策者D。然後，我們將能夠建立一臺機器M，它決定A_TM。在輸入<M', w>，M執行以下操作：（！直到它停止，我們知道，因爲D沒有拒絕）輸入

• 運行D<M',w>
• 如果D拒絕，拒絕，否則就w運行M'
• 如果M'接受，接受，拒絕拒絕。

在那裏，我們看到的矛盾與我們的假設

通用圖靈機

現在你的問題的核心：你居然喂M任何有效的機器描述M'，不一定<M>本身。請記住，TM和「程序」實際上是等價的：請參閱這個不錯的answer瞭解更多詳情。引用相同的答案：「圖靈機是算法的正式模擬」。 圖靈機的一個功能是它們可以被編碼爲一個字符串，允許另一個圖靈機（稱爲「Universal Turing Machine」）來執行它們。由於給定的機器是一種算法，因此您會發現您實際上正在爲您的「頂級」TM程序和您所選擇的輸入提供信息。