計算モデルと計算可能性

決定性有限オートマトン ${M = (Q,\Sigma,\delta,q_0,F)}$

${\Sigma^{\ast}}$ 上の語 ${w}$ に対して ${M}$ を動作させたとき、 ${w}$ を全て読み込んだ後に受理状態であるならば、 ${M}$ は ${w}$ を受理するという。

${M}$ が受理する語の集合を ${L(M)}$ で表し、言語 ${L\,(\subseteq \Sigma^{\ast})}$ が ${M}$ により受理されるとは、 ${L = L(M)}$ となるときをいう。

チューリング機械 ${M = (Q,\Sigma,\Gamma,\delta,q_0,F)}$

${Q}$ は状態の有限集合
${\Gamma}$ はテープ記号の有限集合
${\Sigma \subseteq \Gamma}$ は入力記号の有限集合
${B}$ を空白を表す記号とすると、 ${B \in \Gamma - \Sigma}$
${\delta}$ は ${(Q - F) \times \Gamma}$ から ${Q \times \Gamma \times \{-1,0,1\}}$ への部分関数（遷移関数）
${q_0}$ は ${Q}$ の元（初期状態）
${F}$ は ${Q}$ の部分集合（ ${F}$ の元：受理状態）

遷移関数で定まる次の状況：

チューリング機械 ${M}$ を入力 ${w}$ に対して動作させることを ${M(w)}$ で表す。

チューリング機械が語を受理する：
- 入力 ${w}$ に対して ${M}$ を動作させ、 ${M}$ は有限回動作して受理状態で停止。
チューリング機械が語を拒否する：
- 入力 ${w}$ に対して ${M}$ を動作させ、 ${M}$ は有限回動作して非受理状態で停止。
チューリング機械が言語を受理する：
- ${w \in L \Rightarrow M(w)}$ は受理する。
- ${w \notin L \Rightarrow M(w)}$ は受理しない。
- ${L(M)}$ ： ${M}$ が受理する言語 ${\{ w: M(w)}$ は受理する ${\}}$
チューリング機械が言語を認識する：
- ${w \in L \Rightarrow M(w)}$ は受理する。
- ${w \notin L \Rightarrow M(w)}$ は拒否する。