チューリングマシン
1936年にイギリスの数学者アラン・チューリング（Alan M. Turing）が考案した、計算を行う自動機械の数学的なモデル。形式的な記号操作の組み合わせ、繰り返しで構成されるすべての計算を実行することができる、最も単純化されたコンピュータのモデルとして知られる。 その表面に記号を読み書きできるテープ。長さは無制限（必要になれば順番にいくらでも先にシークできる）とするテープに記号を読み書きするヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトンがある。 テープに読み書きされる有限個の種類の記号最初から（初期状態において）テープにあらかじめ書かれている記号列有限オートマトンの状態遷移規則群。
この機械に外部から、有限個の記号の定義、あらかじめ記号の列が書き込まれたテープ、ヘッドの状態を遷移させる規則の集合（ある「記号-状態」の組み合わせの時にどのような動作を行うかを列挙した表）を与えると、規則に従って次々にヘッドが動作する。
状態遷移表で終了と定義された状態にたどり着くと計算は終了し、その時テープに記載された記号列が計算結果となる。これらは現実のコンピュータにおけるソフトウェア（数学的にはアルゴリズム）に相当する。 チューリングマシンの動作を定義する記号集合や初期状態、遷移表などは何らかの規則に基づいて符号化し、特定の符号の列（例えば0と1の並んだビット列）として表現することができる。 任意の符号化されたチューリングマシンを受け取って、その動作を完全に真似ることができる特殊なチューリングマシンを構成することができ、これを「万能チューリングマシン」（universal Turing machine）という。