知っておきたいＩＴキーワード〜チューリング・マシン
日経コンピュータ　第580号　2003.8.11

　「機械的に計算できる」とはどういうことかを数学的にモデル化した、仮想的な計算機。１９３６年に英国の数学者アラン・チューリングが発表した。アルゴリズムとして定式化できる計算、すなわちプログラムすべてが、このモデルで表現できる。　チューリング・マシンは、「無限に長いテープ」、「そこを左右に動いて読み書きするヘッド」、「有限のパターンの内部状態を持てる制御部」の三つの要素で構成される。ヘッドがテープか…