爲什麼這是一個無效的圖靈機？

Question

在進行考試修改時，我無法回答Sipser所着的「計算理論導論」一書中的以下問題。不幸的是，這本書中沒有解決這個問題的方法。

解釋爲什麼以下不是合法的圖靈機。

M = {

的輸入是在變量x1一個多項式p，...，XN

1. 嘗試X1的所有可能的設置，...，x N爲整數值
2. 在所有這些設置上評估p
3. 如果這些設置中的任何一個評估爲0，則接受;否則拒絕。 }

這讓我瘋狂！我懷疑這是因爲這組整數是無限的？這是否超出了字母表的允許大小？

Answer 1

雖然這是描述一個圖靈機的相當非正式的方式，我想說的問題是下列之一：

• otherwise reject - 我Welbog同意這一點。由於您擁有數量可能無限的可能設置，因此機器無法知道其評估值爲0的設置是否還會到來，並且如果未找到任何設置，將永遠循環 - 只有遇到此類設置時，機器可能會停止。最後的陳述是無用的，永遠不會是真的，除非你將機器限制在一個有限的整數集合中。代碼順序：我會讀這個僞代碼爲「首先寫下所有可能的設置，然後評估每個可能的設置」，並且存在您的問題： 再次，通過擁有無限可能的設置集，甚至不需要第一部分將永遠終止，因爲從來沒有最後的設置寫下來並繼續下一步。在這種情況下，機器甚至不會說「沒有0設置」，但它甚至不能開始評估以找到一個。這也可以通過限制整數集來解決。

無論如何，我不認爲問題是字母表的大小。你不會使用無限的字母表，因爲你的整數可以用十進制/二進制/等寫成，而那些只使用（非常）有限的字母表。

Answer 2

我在圖靈機上有點生疏，但我相信你的推理是正確的，即整數集是無限的，因此你不能計算它們。我不知道如何從理論上證明這一點。然而，讓你的頭在圖靈機周圍的最簡單的方法是記住「真實計算機可以計算的任何東西，圖靈機也可以計算。」。所以，如果你可以編寫一個給定多項式的程序可以解決你的3個問題，你將能夠找到一個也可以做到的圖靈機。

Answer 3

我認爲這個問題是非常最後一部分：otherwise reject.

據countable set basics，在數集的任何向量空間是可數的本身。在你的情況下，你有一個整數大小爲n的向量空間，這是可數的。所以你的整數集是可數的，因此可以嘗試它們的每個組合。 （也就是說不會錯過任何組合）。

而且，在給定的一組輸入上計算p的結果也是可能的。

並且當p評估爲0時進入接受狀態也是可能的。

但是，由於存在無限數量的輸入向量，因此您可以從不拒絕輸入。因此，圖靈機不能遵循問題中定義的所有規則。沒有最後的規則，這是可能的。