圖靈機可以暫停和隱式接受圖靈機不能處理的字符串嗎？

Question

所以我遇到了一個我不確定的問題。爲了好奇，我想問：

我很確定圖靈機可以隱式拒絕它無法處理的字符串，但它可以做補充嗎？換句話說，它可以暗含接受它不能處理的輸入？我很抱歉，如果這是一個愚蠢的問題，我似乎無法找到答案。

Answer 1

這不是一個愚蠢的問題！我相信「無法處理的字符串」的含義實際上是「沒有有效格式的字符串」，我認爲它是「含有我們不知道的符號的字符串」。 （我要走出this presentation的幻燈片14，我只是用google搜索Turing 'implicitly reject'）。因此，如果我們使用該定義，那麼我們需要簡單地創建一個圖靈機器，它接受一個輸入，如果它包含的符號不在我們的有效集合中。

是的，還有其他可能的解釋「它不能處理的字符串」，但我相當肯定這意味着這一點。它顯然不能沒有約束的定義，否則我們可以定義「不能處理的字符串」，例如「表示停止的程序的字符串」，並且我們已經解決了暫停問題！ （或者如果你不熟悉暫停問題，你可以替代任何NP完全問題，真的）。

我認爲拒絕字符串圖靈機的想法不能處理的原因是首先引入的是，使得機器可以在所有輸入上被很好地定義。所以說，如果你有一個圖靈機接受一個二進制數，如果它可以被3整除，但你傳遞的不是一個雙數的輸入（比如說「蘋果醬」），我們仍然可以推理輸出的程序。