所以我遇到了一個我不確定的問題。爲了好奇,我想問:圖靈機可以暫停和隱式接受圖靈機不能處理的字符串嗎?
我很確定圖靈機可以隱式拒絕它無法處理的字符串,但它可以做補充嗎?換句話說,它可以暗含接受它不能處理的輸入?我很抱歉,如果這是一個愚蠢的問題,我似乎無法找到答案。
所以我遇到了一個我不確定的問題。爲了好奇,我想問:圖靈機可以暫停和隱式接受圖靈機不能處理的字符串嗎?
我很確定圖靈機可以隱式拒絕它無法處理的字符串,但它可以做補充嗎?換句話說,它可以暗含接受它不能處理的輸入?我很抱歉,如果這是一個愚蠢的問題,我似乎無法找到答案。
這不是一個愚蠢的問題!我相信「無法處理的字符串」的含義實際上是「沒有有效格式的字符串」,我認爲它是「含有我們不知道的符號的字符串」。 (我要走出this presentation的幻燈片14,我只是用google搜索Turing 'implicitly reject'
)。因此,如果我們使用該定義,那麼我們需要簡單地創建一個圖靈機器,它接受一個輸入,如果它包含的符號不在我們的有效集合中。
是的,還有其他可能的解釋「它不能處理的字符串」,但我相當肯定這意味着這一點。它顯然不能沒有約束的定義,否則我們可以定義「不能處理的字符串」,例如「表示停止的程序的字符串」,並且我們已經解決了暫停問題! (或者如果你不熟悉暫停問題,你可以替代任何NP完全問題,真的)。
我認爲拒絕字符串圖靈機的想法不能處理的原因是首先引入的是,使得機器可以在所有輸入上被很好地定義。所以說,如果你有一個圖靈機接受一個二進制數,如果它可以被3整除,但你傳遞的不是一個雙數的輸入(比如說「蘋果醬」),我們仍然可以推理輸出的程序。