2009-8 第4問 (5)

チューリングマシンは無限に長いテープとそのテープを読み書きするヘッド、及び内部状態を保持するためのメモリからなる。チューリングマシンはその内部状態に従ってヘッドを動かし、テープから情報を読んで状態を変更したり、テープに情報を書き込んだりする。
チューリングマシンの動作は非常に単純だが、チューリングマシンで解くことのできる問題のクラスは実際の計算機の解くことのできる問題のクラスと同一であり、計算機のモデルとしてよく利用される。