帰納的言語

$M=(\Sigma,\Gamma,Q,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}})$ を $L$ の判定機とし、受理状態と拒否状態の役割を入れ替えた機械 $\overline{M}:=(\Sigma,\Gamma,Q,\delta,q_0,q_{\mathrm{rej}},q_{\mathrm{acc}})$ を考える。次の様相は「状態が $\{q_{\mathrm{acc}},q_{\mathrm{rej}}\}$ に属さない様相に $\delta$ を施す」ことで定まり、この二元集合は入れ替えで変わらない。したがって $M$ と $\overline{M}$ は同じ入力から同じ様相の列をたどり、同じステップ数で同じ状態に入って停止する。その状態の意味だけが逆になる。$M$ はすべての入力で停止し、$w\in L$ なら $q_{\mathrm{acc}}$、$w\notin L$ なら $q_{\mathrm{rej}}$ で停止するので、$\overline{M}$ はすべての入力で停止し、$w\in\overline{L}$ なら受理し、$w\notin\overline{L}$ なら拒否する。よって $\overline{M}$ は $\overline{L}$ の判定機である。$\square$

正規言語は有限オートマトンで認識され（正規言語 の記事の命題「右線形文法と有限オートマトンの同値性」）、さらに決定性有限オートマトンで認識される（有限オートマトン の記事の命題「$\varepsilon$ 遷移の除去」「部分集合構成」）。そこで後半を示せばよい。
$\mathcal{A}=(S,\Sigma,\eta,s_0,F)$ を決定性有限オートマトンとし（$\eta\colon S\times\Sigma\to S$。文字列への拡張も $\eta$ と書く）、$S$ に属さない二つの新しい元 $q_{\mathrm{acc}},q_{\mathrm{rej}}$ をとる。$\Gamma:=\Sigma\cup\{\sqcup\}$、$Q:=S\cup\{q_{\mathrm{acc}},q_{\mathrm{rej}}\}$ として、1 テープの機械 $M=(\Sigma,\Gamma,Q,\delta,s_0,q_{\mathrm{acc}},q_{\mathrm{rej}})$ の遷移を
$$ \delta(s,a):=(\eta(s,a),a,\mathrm{R})\quad(s\in S,\ a\in\Sigma),\qquad\delta(s,\sqcup):=\begin{cases}(q_{\mathrm{acc}},\sqcup,\mathrm{N})&(s\in F)\\(q_{\mathrm{rej}},\sqcup,\mathrm{N})&(s\notin F)\end{cases} $$
で定める（$q_{\mathrm{acc}},q_{\mathrm{rej}}$ での値は使われないので任意に定める）。
入力 $w=w_1\cdots w_n$ について、$0\le i\le n$ のとき「$i$ ステップ後の様相は、状態 $\eta(s_0,w_1\cdots w_i)$、テープは初期のまま、ヘッドは $i$ 番目」であることを $i$ についての帰納法で示す。$i=0$ は初期様相そのものである（$\eta(s_0,\varepsilon)=s_0$）。$i< n$ で成り立つとすると、状態は $S$ に属し、ヘッドは $w_{i+1}$ を読むので、$M$ は $w_{i+1}$ をそのまま書いて右へ動き、状態は $\eta(\eta(s_0,w_1\cdots w_i),w_{i+1})=\eta(s_0,w_1\cdots w_{i+1})$ になる。$i=n$ のときヘッドは $n$ 番目の空白を読むので、$n+1$ ステップ目に、$\eta(s_0,w)\in F$ なら $q_{\mathrm{acc}}$、そうでなければ $q_{\mathrm{rej}}$ に入って停止する。決定性有限オートマトンが $w$ を受理することは $\eta(s_0,w)\in F$ と同値である（有限オートマトン の記事の定義「非決定性有限オートマトンと決定性有限オートマトン」）から、$M$ は $L(\mathcal{A})$ の判定機である。$\square$

（機械の構成）$P$ のテープ $1,\dots,k_1$ で $M_1$ を、テープ $k_1+1,\dots,k_1+k_2$ で $M_2$ を模倣する。$\Gamma:=\Gamma_1\cup\Gamma_2$ とし、$Q_1\times Q_2$ に属さない新しい状態 $c,b,q_{\mathrm{acc}},q_{\mathrm{rej}}$ をとって $Q:=\{c,b,q_{\mathrm{acc}},q_{\mathrm{rej}}\}\cup(Q_1\times Q_2)$、初期状態を $c$ とする。読んだ記号の列を $(\vec x_1,\vec x_2)\in\Gamma^{k_1}\times\Gamma^{k_2}$ と書く。遷移関数を次で定める。

• 写しの段階（$a\in\Sigma$）：状態 $c$ でテープ 1 とテープ $k_1+1$ の記号の組が $(a,\sqcup)$ なら、テープ $k_1+1$ に $a$ を書いてこの二本のヘッドを右へ動かし、状態 $c$ のまま。組が $(\sqcup,\sqcup)$ なら二本のヘッドを左へ動かして状態 $b$ へ。状態 $b$ で組が $(a,a)$ なら二本のヘッドを左へ動かし、状態 $b$ のまま。組が $(\sqcup,\sqcup)$ なら二本のヘッドを右へ動かして状態 $(q_0^{(1)},q_0^{(2)})$ へ。いずれもほかのテープは読んだ記号をそのまま書いてヘッドを動かさない。
• 模倣の段階：状態 $(r_1,r_2)\in Q_1\times Q_2$ で $(\vec x_1,\vec x_2)$ を読んだとき、各 $i$ について、$r_i\notin H_i$ かつ $\vec x_i\in\Gamma_i^{k_i}$ なら $(r_i',\vec y_i,\vec D_i):=\delta_i(r_i,\vec x_i)$、そうでなければ $(r_i',\vec y_i,\vec D_i):=(r_i,\vec x_i,(\mathrm{N},\dots,\mathrm{N}))$ とおく。$P$ は $(\vec y_1,\vec y_2)$ を書いて $(\vec D_1,\vec D_2)$ のとおりに動き、$(r_1',r_2')\notin E$ なら状態 $(r_1',r_2')$ へ、$(r_1',r_2')\in E$ なら $d(r_1',r_2')=\mathrm{acc},\mathrm{rej}$ に応じて $q_{\mathrm{acc}},q_{\mathrm{rej}}$ へ移る。
• 上に挙げない組では値を任意に定める。
  （正しさ）写しの段階で入力をテープ $k_1+1$ に写し、$2|w|+2$ ステップ後に二台の初期様相がそろう。そこから $n$ ステップ後の $P$ の様相は、まだ $E$ に入っていない限り、$M_1$ と $M_2$ のそれぞれ $\min(n,t_{M_i}(w))$ ステップ後の様相を並べたものになる。これを $n$ についての帰納法で確かめれば 1・2 が従う。
  帰納法の細部を開く

  （写しの段階）$m:=|w|$ とする。状態 $c$ で $j$ ステップ（$0\le j\le m$）進んだ後、テープ 1 は初期のままで、テープ $k_1+1$ の $0,\dots,j-1$ 番目に $w_1,\dots,w_j$、ほかは空白であり、二本のヘッドは $j$ 番目にある。$j=m$ で $(\sqcup,\sqcup)$ を読んで状態 $b$ に移り、ヘッドは $m-1$ 番目に来る。状態 $b$ では二本のテープの同じマスに同じ文字があるので左へ戻り続け、$-1$ 番目で $(\sqcup,\sqcup)$ を読んでヘッドを $0$ 番目に戻す（$m=0$ でも同じである）。こうして $2m+2$ ステップ後に、状態 $(q_0^{(1)},q_0^{(2)})$ で、テープ $1,\dots,k_1$ は $M_1$ の、テープ $k_1+1,\dots,k_1+k_2$ は $M_2$ の、入力 $w$ の初期様相と同じ内容とヘッドの位置になる。

  （模倣の段階）$t_{M_i}(w)$ は状態が初めて $H_i$ に入るステップ数であり、$q_0^{(i)}\notin H_i$ なので、$R_i(n)\in H_i$ は $t_{M_i}(w)\le n$ と同値である。とくに $(R_1(0),R_2(0))=(q_0^{(1)},q_0^{(2)})\notin E$ である。$n\in\mathbb{N}$ について、主張 $(\ast)_n$ を「$1\le n'\le n$ のすべての $n'$ で $(R_1(n'),R_2(n'))\notin E$ ならば、$P$ の $2m+2+n$ ステップ後の様相は、状態 $(R_1(n),R_2(n))$ で、$M_i$ を模倣するテープの内容とヘッドの位置は $M_i$ の $\min(n,t_{M_i}(w))$ ステップ後のもの（$i=1,2$）である」とし、帰納法で示す。$n=0$ は写しの段階で示した。$(\ast)_n$ が成り立ち、仮定が $n+1$ まで成り立つとする。$M_i$ を模倣するテープの記号は $M_i$ の様相のものなので $\Gamma_i$ に属する。$R_i(n)\notin H_i$ なら $t_{M_i}(w)>n$ であり、$P$ は $\delta_i$ をそのまま施すので、その部分は $M_i$ の $n+1=\min(n+1,t_{M_i}(w))$ ステップ後のものになる。$R_i(n)\in H_i$ なら $t_{M_i}(w)\le n$ であり、$P$ はその部分も状態の第 $i$ 成分も変えないので、$M_i$ の $t_{M_i}(w)=\min(n+1,t_{M_i}(w))$ ステップ後のままである。どちらの場合も新しい組は $(R_1(n+1),R_2(n+1))$ であり、これは仮定により $E$ に属さないので、$P$ の状態はこの組になる。よって $(\ast)_{n+1}$ が成り立つ。

  1 の場合：$n^{*}\ge1$ であり、$(\ast)_{n^{*}-1}$ の様相から上と同じ計算で、次の一歩の新しい組は $(R_1(n^{*}),R_2(n^{*}))\in E$ となる。$P$ は $2m+2+n^{*}$ ステップ目に $d$ の値に応じた $q_{\mathrm{acc}}$ または $q_{\mathrm{rej}}$ に入って停止する。それ以前の状態は $c,b$ か $Q_1\times Q_2$ の元なので、それ以前には停止しない。2 の場合：すべての $n$ で $(\ast)_n$ が成り立ち、$P$ の状態は写しの段階の後つねに $Q_1\times Q_2$ に属するので、$P$ は停止しない。$\square$

記号は lem-rl-parallel のとおりとする。
1：$M_i$ を $L_i$ の判定機とする。$t_{M_i}(w)<\infty$ であり、$n\ge t_{M_i}(w)$ なら $R_i(n)$ は $M_i$ が停止したときの状態なので、$R_i(n)=q_{\mathrm{acc}}^{(i)}$ は $w\in L_i$ と同値である。$E:=H_1\times H_2$ とおくと、$(R_1(n),R_2(n))\in E$ となる最小の $n$ は $\max(t_{M_1}(w),t_{M_2}(w))$ である。$d(r_1,r_2)$ を「$r_1=q_{\mathrm{acc}}^{(1)}$ または $r_2=q_{\mathrm{acc}}^{(2)}$」のとき $\mathrm{acc}$、そうでないとき $\mathrm{rej}$ と定めれば、lem-rl-parallel の $P$ はすべての入力で停止して $L_1\cup L_2$ を判定する。「$r_1=q_{\mathrm{acc}}^{(1)}$ かつ $r_2=q_{\mathrm{acc}}^{(2)}$」のとき $\mathrm{acc}$ と定めれば $L_1\cap L_2$ を判定する。$L_1\setminus L_2=L_1\cap\overline{L_2}$ は、prop-rl-complement と共通部分の場合から帰納的である。
2：$M_i$ を $L_i$ を受理する機械とする。受理状態に入ればそれ以後 $R_i$ は変わらないので、ある $n$ で $R_i(n)=q_{\mathrm{acc}}^{(i)}$ となることは $w\in L_i$ と同値である。和については $E:=\{(r_1,r_2)\mid r_1=q_{\mathrm{acc}}^{(1)}\ \text{または}\ r_2=q_{\mathrm{acc}}^{(2)}\}$、共通部分については $E:=\{(q_{\mathrm{acc}}^{(1)},q_{\mathrm{acc}}^{(2)})\}$ とし、どちらも $d$ を恒等的に $\mathrm{acc}$ とする。lem-rl-parallel により、$P$ が $w$ を受理するのは $(R_1(n),R_2(n))\in E$ となる $n$ があるときちょうどであり、それはそれぞれ $w\in L_1\cup L_2$、$w\in L_1\cap L_2$ と同値である。よって $L(P)$ は求める言語である。$\square$

1 から 2：判定機は $L$ を受理する機械でもあるので $L$ は帰納的可算である。prop-rl-complement により $\overline{L}$ も帰納的言語なので、帰納的可算である。
2 から 1：$M_1$ を $L$ を受理する機械、$M_2$ を $\overline{L}$ を受理する機械とする。lem-rl-parallel を
$$ E:=\{(r_1,r_2)\mid r_1=q_{\mathrm{acc}}^{(1)}\ \text{または}\ r_2=q_{\mathrm{acc}}^{(2)}\},\qquad d(r_1,r_2):=\begin{cases}\mathrm{acc}&(r_1=q_{\mathrm{acc}}^{(1)})\\\mathrm{rej}&(r_1\ne q_{\mathrm{acc}}^{(1)})\end{cases} $$
に適用して $P$ を作る。$w\in L$ のとき、$M_1$ は $w$ を $t_{M_1}(w)$ ステップで受理する。$w\notin\overline{L}$ なので $M_2$ は $w$ を受理せず、すべての $n$ で $R_2(n)\ne q_{\mathrm{acc}}^{(2)}$ である。また $n< t_{M_1}(w)$ では $R_1(n)\notin H_1$ である。よって $(R_1(n),R_2(n))\in E$ となる最小の $n$ は $t_{M_1}(w)$ で、そのとき $R_1(n)=q_{\mathrm{acc}}^{(1)}$ なので $P$ は受理する。$w\notin L$ のとき、$M_1$ は $w$ を受理しないのですべての $n$ で $R_1(n)\ne q_{\mathrm{acc}}^{(1)}$ であり、$w\in\overline{L}$ なので $M_2$ は $t_{M_2}(w)$ ステップで受理する。同様に最小の $n$ は $t_{M_2}(w)$ で、$R_1(n)\ne q_{\mathrm{acc}}^{(1)}$ なので $P$ は拒否する。したがって $P$ はすべての入力で停止する $L$ の判定機である。$\square$

$A_{\mathrm{TM}}$ は帰納的可算である（ex-rl-nonexamples）。$\overline{A_{\mathrm{TM}}}$ も帰納的可算なら、thm-rl-post により $A_{\mathrm{TM}}$ は帰納的言語になり、$A_{\mathrm{TM}}$ が帰納的でないこと（ex-rl-nonexamples）に反する。$\square$

句構造言語 の記事の定理「Turing 機械との同値性」により、句構造言語であることと帰納的可算言語であることは同値である。あとは thm-rl-post による。$\square$

状態とテープ記号の名前を付け替えても、様相の列は名前を付け替えたものになるだけなので、受理・拒否・停止は変わらない。新しい記号 $\gamma_1,\gamma_2,\dots$ を固定する。各 $L\in\mathcal{RE}(\Sigma)$ について、$Q=\{0,1,\dots,p-1\}$（$p\ge3$、$q_0=0$、$q_{\mathrm{acc}}=1$、$q_{\mathrm{rej}}=2$）、$\Gamma=\Sigma\cup\{\sqcup,\gamma_1,\dots,\gamma_g\}$（$g\in\mathbb{N}$）の形の $k$ テープの機械 $M$ で $L(M)=L$ となるものがある。$(k,p,g)$ を固定すると、この形の機械は遷移関数 $\delta\colon Q\times\Gamma^{k}\to Q\times\Gamma^{k}\times\{\mathrm{L},\mathrm{R},\mathrm{N}\}^{k}$ で決まり、有限集合から有限集合への写像は有限個しかないので、有限個である。$(k,p,g)$ の選び方は可算個なので、この形の機械全体は高々可算であり、$M\mapsto L(M)$ はそこから $\mathcal{RE}(\Sigma)$ への全射である。よって $\mathcal{RE}(\Sigma)$ とその部分集合 $\mathcal{R}(\Sigma)$ は高々可算である。$\Sigma\ne\emptyset$ なので有限言語は無限個あり、それらはすべて帰納的言語である（ex-rl-examples）から、二つとも可算無限集合である。一方、$\Sigma$ 上の言語全体は非可算集合である（形式言語 の記事の命題「言語の個数」）から、$\mathcal{RE}(\Sigma)$ に属さない言語が存在する。$\square$