調査員（コンピュータサイエンス）

列挙子は、プリンターが接続されたチューリング マシンです。チューリング マシンは、そのプリンターを出力デバイスとして使用して文字列を印刷できます。チューリング マシンがリストに文字列を追加するたびに、その文字列がプリンターに送信されます。列挙子はチューリング マシンのバリアントの一種であり、チューリング マシンと同等です。

列挙子は、言語が である2 テープ チューリング マシン (マルチテープ チューリング マシン、 ) として定義できます。最初、 は入力を受け取らず、すべてのテープは空白です (つまり、空白の記号で埋められています)。新しく定義された記号は、の要素の終わりを示す区切り文字です。2 番目のテープはプリンタと見なすことができ、その上の文字列は で区切られます。によって示される列挙子によって列挙される言語は、2 番目のテープ (プリンタ) 上の文字列の集合として定義されます。 ${\displaystyle E}$${\displaystyle k=2}$${\displaystyle \emptyset}$${\displaystyle E}$${\displaystyle \#\in \Gamma \land \#\notin \Sigma }$${\displaystyle S}$${\displaystyle \#}$${\displaystyle E}$${\displaystyle L(E)}$

有限アルファベット上の言語は、列挙子によって列挙できる場合にのみチューリング認識可能です。これは、チューリング認識可能な言語は再帰的に列挙可能であることも示しています。

証拠

チューリング認識可能な言語は列挙子によって列挙できる

チューリングマシンと、それが受け入れる言語を考えてみましょう。入力アルファベット上のすべての可能な文字列の集合、つまりクリーネ閉包は可算集合なので、その中の文字列をなどとして列挙できます。次に、言語を列挙する Enumerator は、次の手順に従います。 ${\displaystyle M}$${\displaystyle L(M)}$${\displaystyle \Sigma }$${\displaystyle \Sigma^{*}}$${\displaystyle s_{1},s_{2},\dots ,s_{i},}$${\displaystyle L(M)}$

1 （i = 1,2,3、...の場合）
2入力文字列で実行 -ステップ${\displaystyle M}$  ${\displaystyle s_{1},s_{2},\dots ,s_{i}}$  ${\displaystyle i}$
3 文字列が受け入れられた場合は、それを出力します。

ここで、言語内のすべての文字列が、私たちが構築した Enumerator によって印刷されるかどうかという疑問が生じます。言語内の任意の文字列について、 TM はそれを受け入れるために有限数のステップ (の場合とします) を実行します。次に、Enumerator の - 番目のステップでが印刷されます。したがって、Enumerator は認識したすべての文字列を印刷しますが、1 つの文字列が複数回印刷されることもあります。 ${\displaystyle L(M)}$${\displaystyle w}$${\displaystyle L(M)}$${\displaystyle M}$${\displaystyle k}$${\displaystyle w}$${\displaystyle k}$${\displaystyle w}$${\displaystyle M}$

列挙可能な言語はチューリング認識可能

列挙可能な言語を認識するチューリング マシンを構築するのは非常に簡単です。 2 つのテープを用意します。 1 つのテープで入力文字列を取得し、もう 1 つのテープで列挙子を実行して、言語の文字列を 1 つずつ列挙します。 2 番目のテープに文字列が印刷されると、それを 1 番目のテープの入力と比較します。 一致した場合は入力を受け入れ、一致しなかった場合は続行します。文字列が言語にない場合は、チューリング マシンが停止することはなく、文字列を拒否することに注意してください。 ${\displaystyle M}$${\displaystyle L}$