計算可能性理論
計算可能性理論の中心課題に答えるために、「コンピュータとは何か」を形式的に定義する必要がある。利用可能な計算モデルはいくつか存在する。以下に代表例を挙げる。
計算の各ステップが前のステップの半分の時間しかかからない機械を考える。第一ステップにかかる時間を 1 に正規化すると、実行にかかる時間は
1 + 1 2 + 1 4 + ⋯ {\displaystyle 1+{1 \over 2}+{1 \over 4}+\cdots }
となる。この無限数列の総和は 2 に近づいていく。つまり、このチューリングマシンは 2 単位の時間内に無限の処理を実行できる。この機械は、対象となる機械の実行を直接シミュレーションすることで停止問題の判定が可能である。
チューリングマシンは任意の文脈自由言語を判定できるだけでなく、プッシュダウン・オートマトンが判定できない言語(例えば素数の集合からなる言語)も判定可能である。したがってチューリングマシンはさらに強力な計算モデルと言うことができる。
チューリングマシンでは、入力テープに「バックアップ」を置くことができるため、上で説明した計算モデルには不可能な方法で動作可能である。入力に対して停止しないチューリングマシンを構築することもできる。チューリングマシンはあらゆる入力について停止して答え(言語と入力の判定)を返す機械である。このようにチューリングマシンが必ず停止する言語クラスを帰納言語と呼ぶ。ある言語に含まれる文字列を与えられたときには停止するが、その言語に含まれない文字列を与えられたときに停止しない可能性があるというチューリングマシンもある。このような言語を帰納的可算言語と呼ぶ。
チューリングマシンは非常に強力な計算モデルである。