チューリングマシン
有限集合 Q の元 q ∈ Q を状態 (state) という。
言語を認識するだけでなく、 Σ ∗ {\displaystyle {\mathit {\Sigma }}^{*}} から Σ ∗ {\displaystyle {\mathit {\Sigma }}^{*}} への部分函数 f {\displaystyle f} を計算する機械を考えることもできる。すなわち機械 M {\displaystyle M} は、各 x ∈ d o m ( f ) {\displaystyle x\in \mathrm {dom} (f)} に対しては文字列 f ( x ) {\displaystyle f(x)} をテープに書いてから初めて受理状態へ移り、 x ∉ d o m ( f ) {\displaystyle x\notin \mathrm {dom} (f)} に対しては決して受理状態へ移らない。このような M {\displaystyle M} が存在するとき、 f {\displaystyle f} は部分帰納的あるいは計算可能(computable)であるという。
遷移関数 δ {\displaystyle \delta } において、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値(すなわちその時にすべき動作)が、高々一つならば、そのチューリングマシンは「決定的」(deterministic)である。これに対し、動作が複数の場合は「非決定的」(non-deterministic)であり、受理の意味も再定義して、非決定的チューリングマシンや乱択チューリングマシンが定義される。また、未来と過去を逆にしても決定的であるのが可逆チューリングマシンである。
チューリングマシン M は次の7つ組で定義される:
M = ⟨ Q , Γ , b , Σ , δ , q i n i t , q a c c ⟩ . {\displaystyle M=\langle Q,{\mathit {\Gamma }},b,{\mathit {\Sigma }},\delta ,q_{\mathrm {init} },q_{\mathrm {acc} }\rangle \,.}