計算

チューリングマシン

1936年、アラン・チューリングが論文『計算可能数について』で提示した抽象的計算機械のモデル。テープ・読み書きヘッド・状態遷移規則からなる単純な機械で、あらゆるアルゴリズム的計算を実行できる。計算可能性の理論的定義を与え、停止問題の決定不能性を証明し、現代計算機の数学的基礎となった。