万能チューリング機械の説明として、適切なものはどれか。

解説

正解は「任意のチューリング機械の記述と入力を受け取り、その動作を模倣できる」です。チューリング機械の状態遷移の規則は記号列として符号化できるので、それをテープ上のデータとして読み込み、1ステップずつ模倣する1台のチューリング機械を作れます。これは、プログラムをデータとしてメモリに置いて実行するプログラム内蔵方式のコンピュータの理論的な原型です。「状態の数が無限にある」は定義に反し、万能チューリング機械も有限個の状態しかもちません。「すべての問題を有限時間で解くことができる」機械は存在しません。「複数本のテープをもち、1本の場合より多くの関数を計算できる」も誤りで、多テープでも計算できる関数の範囲は変わりません。