固定出力を備えた米の定理

Question

だから私は米の定理の助けを借りて言語があることを証明することになっていました： $ L_ {5}={w \ {0,1 \} ^ {*} | \ forall x \ in \ {0,1 \} ^ {*}、 m_ {w}（w）= x \} $ は決定可能です。

まず第一に、私たちが最初に米の定理を使うことができるのは理解していません。私が2つの裂け目を選択した場合 $ m_ {w} $ $ {w '} $ $ $ w \ neq w' $ それから私は $ m_ {w}（w）= m_ {w '}（w）= x $ 。しかし、これは $ w '$ につながりません $ l_ {5} $ と $ w \ in l_ {5} $ 。それとも私は何かを誤解していますか？

2番目：解決策は、言語 $ l_ {5} $ が $ l_ {5}として決定可能です。出力は固定入力で明確に決定されているため、=emptyset $ 。 しかし、なぜそれはそうですか？ $ l_ {5} $ が空でないと思いました。それ自身の入力にxを出力するTMがあり、いくつかはありません。

Answer 1

$ w $ は $ l_5 $ の場合、すべて $ x \ in \ {0,1 \} ^ * $ $ m_w（w）= x $ の場合です。特に、l_5 $ で $ w \の場合、 $ m_w（w）= 0 $ と $ m_w（w）= 1 $ 。どちらも真実ではありません。そのため、 $ L_5 $ に属していません。