句構造文法と万能TMについて - はてぃーぽったーの備忘録

今回は句構造文法（生成規則 $P$ に対する制限がない文法）と万能TMについてお話していきます。

句構造文法とTM
万能TM

句構造文法とTM

f:id:mkwamezaki1007:20190119193245p:plain

証明のお気持ちは上図にほとんど集約されています。

TM $M$ を、句構造文法 $G$ の開始記号 $S$ および $w\in L(G)$ を入力とし、 $S$ に対する書き換えを行っていった結果 $w$ と一致するものが得られた時は入力 $(S, w)$ を受理するとします。

まず、 $L(G)\subset L(M)$ を示します。

$w\in L(G)$ , つまり $G$ が生成する記号列 $w$ を取ります。

入力記号列 $w$ の後に区切り記号と開始記号 $S$ を置き、生成規則に対応するような次動作関数を定義することにより $S$ を書き換えていきます。 $S$ から $w$ を導出するような生成規則の適用経路は $w\in L(G)$ より必ず存在するため、 $M$ は入力 $(S, w)$ を受理します。よって、 $L(G)\subset L(M)$ です。

次に $L(G)\supset L(M)$ を示します。

$M$ が受理する記号列 $w\in L(M)$ に対して、受理するまでの動作は $G$ が $w$ を生成する過程になっています。（つまり、 $M$ の動作ではヘッドの指し示す位置の記号を書き換えていきますが、この書き換えを生成規則に変換してあげればいいです。）これによって $L(G)\supset L(M)$ が示され、 $L(G)=L(M)$ となります。細かな $M$ の動作については割愛していますが、この辺りは適宜手元の資料を参照してください。

万能TM

次に万能TMについてです。まず、万能というのは認識能力が他のモデルと異なるということではありません（ TMのモデルの等価性の記事を参照）。これは、ある万能TM: $U$ は任意のTM: $M$ をエミュレートすることができるということです。今までは特定のTM: $M$ に対する入力記号列 $w$ を考えてきましたが、万能TM: $U$ の入力はそういったTM: $M$ および記号列 $w$ であり、入力は $\langle M,w \rangle$ と書きます。

$M$ が $w$ を受理するならば $U$ は $\langle M,w\rangle$ を受理

$M$ が $w$ を拒否するならば $U$ は $\langle M,w\rangle$ を拒否

つまり、記号列 $w$ に対して入力されたTM: $M$ を動作させているわけです。他のTMも同様に入力として受け取れるので、結果として任意のTMをエミュレートできるわけですね。これが万能TMの考え方です。

ただ、一つ気を付けたいのはあくまで $U$ はただのTMなので、 $M$ をそのまま動かせるわけではありません。TMはあくまで記号列を入力とするので、 $M$ 自体も記号列に変換する、いわゆる「コード化」という作業が必要です。ただ、万能TMを使用した証明の際にはコード化の中身にまで言及する必要は無いので、 $M$ の動作の記述には高レベルな記述を用いることが多いと思います。

次回は決定性のお話です。

編集履歴:

2020/10/26 全体的な表現の見直し