試験の復習をしているときに、Sipser 著「An Introduction to the Theory of Computation」という本からの次の質問に答えるのに苦労しています。残念ながら、本書にはこの問題の解決策はありません。
以下が正当なチューリング マシンではない理由を説明してください。
M = {
入力は、変数 x1、...、xn 上の多項式 p です。
これは私を夢中にさせています！整数のセットが無限だからだと思いますか? これはどういうわけかアルファベットの許容サイズを超えていますか?
問題は最後の部分にあると思います：otherwise reject.
可算集合の基本に従って、可算集合上のベクトル空間はそれ自体可算です。あなたの場合、n数えられる size の整数を超えるベクトル空間があります。したがって、整数のセットは可算であるため、それらのすべての組み合わせを試すことができます。（つまり、どの組み合わせも見逃すことはありません。）
また、p与えられた入力セットの結果を計算することも可能です。
また、 が 0 に評価されたときに受け入れ状態になるpことも可能です。
ただし、入力ベクトルは無数にあるため、入力を拒否することはできません。したがって、質問で定義されたすべての規則に従うことができるチューリング マシンはありません。その最後のルールがなければ、それは可能です。
私はチューリングマシンに少し慣れていませんが、あなたの推論は正しいと思います。つまり、整数のセットは無限であるため、すべてを計算することはできません。ただし、これを理論的に証明する方法はわかりません。
ただし、チューリング マシンを理解するための最も簡単な方法は、「実際のコンピューターが計算できるものは何でも、チューリング マシンも計算できる」ということを覚えておくことです。したがって、与えられた多項式で 3 つの質問を解決できるプログラムを作成できれば、それを実行できるチューリング マシンを見つけることができます。