チューリングマシン
https://upload.wikimedia.org/wikipedia/commons/5/5c/Bombe-rebuild.jpg
Photo CC BY-SA 3.0 Tom Yates
計算可能な問題はすべてチューリングマシンで計算が可能である計算機械の理想モデル。無限の節からなる長いテープと，各節に記録された一つの記号を読み書きするヘッドから構成されヘッドから記号を読み込み，現在の状態と読み込んだ記号に従って，ヘッドの位置に記号を書き込み，内部状態の変更し，ヘッドをどちらかに動かすという一連の動作を，内部状態が停止状態になるまで繰り返す。
そもそも、なぜチューリングはあらゆるものを計算しようとする機械（万能マシン）を考え出したのか。その背景には数学者ヒルベルトが出した、数学を完璧にしよう、数学で解けない問題はない という「ヒルベルト・プログラム（決定問題）」があった。それに対し「数学には解けない問題がある」ことを示すために、チューリングマシンの発想に至った。 wikipedia
解説
解説