チューリング機械の構成要素として、適切な組合せはどれか。

解説

正解は「有限個の状態をもつ制御部、無限長のテープ、テープ上を左右に動くヘッド」です。チューリング機械は、現在の状態とヘッドが読んだ記号に応じて、記号を書き換え、ヘッドを左右に1マス動かし、次の状態に移る計算モデルです。テープは読み書きでき必要なだけ使えるため、コンピュータで計算できることはすべて計算できると考えられています。「有限個の状態をもつ制御部と、1本のスタック」はプッシュダウンオートマトンです。「有限個の状態をもつ制御部と、読み取り専用で右にだけ進む入力テープ」は有限オートマトンです。「無限個の状態をもつ制御部と、有限長のテープ」は定義と逆で、状態は有限個でなければなりません。