チューリングマシン
この節では、チューリングマシンを形式的(formal)に記述する。
チューリングマシン M が入力文字列 x ∈ Σ を受理するまで遷移函数を作用させる最小の回数をチューリングマシン M の入力文字列 x に対する実行時間とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する記憶領域量という。
M が言語 L ⊆ Σ ∗ {\displaystyle L\subseteq {\mathit {\Sigma }}^{*}} を認識するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は帰納可枚挙(recursively enumerable)あるいは計算可枚挙(computably enumerable)であるという。L と Σ ∗ ∖ L {\displaystyle {\mathit {\Sigma }}^{*}\setminus L} がともに帰納可枚挙であるとき、Lは帰納的(recursive)あるいは決定可能(decidable)であるという。
より精細に、自然数から自然数への写像 t に対し、M が L を時間計算量[ないし空間計算量]t で認識するとは、M が L を認識し、かつ各 x ∈ L {\displaystyle x\in L} に対する M {\displaystyle M} の実行時間[ないし記憶領域量]が t ( | x | ) {\displaystyle t(\left|x\right|)} 以下であることをいう。ここで | x | {\displaystyle \left|x\right|} は文字列 x の長さを表す。
「チューリングマシン M が入力文字列 x ∈ Σ ∗ {\textstyle x\in \Sigma ^{*}} を受理(accept)する」とは、チューリングマシン M が初期状態 qinit で入力文字列 x が与えられた状況 q i n i t x b b ⋯ {\textstyle q_{\mathrm {init} }xbb\cdots } に対し、遷移函数 δ を有限回作用させ受理状態 qacc へ遷移した状況 q a c c b b ⋯ {\textstyle q_{\mathrm {acc} }bb\cdots } が得られることをいう。