[補足] チューリング・マシン

1930 年代に計算可能性の概念を導入するために チューリングによって考案された抽象的な機械。

• チューリング・マシン： 有限個数の「内部状態」をもち、 大きさに制限のない入力 (「テープ」) を受取るような機械。 マシンはテープの内容を読むことができ、演算操作の一部としてテープを 前後に動かすこともできる。さらに、テープに新しいマークを書き込む ことや、消すこともできる。

この数学的に定義された (上の説明は全然数学的ではないですが…) 機械で実現可能な演算のことを「アルゴリズム」と呼ぶ。

図 9: チューリング・マシン

このチューリングマシンに何ができるか (計算可能性の問題) を考えて行くと 「あるクラスの数学的問題の全てに答えるアルゴリズムは存在しない」 という結論が導き出される。 (チューリング・マシンの停止問題)

なお、レジスタ、メモリをそれぞれチューリング・マシンの「内部状態」 および「テープ」に対応させて考えると、現在のコンピュータが このチューリング・マシンの非常に良い近似になっていることがわかる。