Теорема риса для машины Turging с фиксированным выходом

Question

Итак, я должен был доказать с помощью теоремы Риса, будь то язык: $ l_ {5}={w \ in \ {0,1 \} ^ {*} | \} ^ {*} | \ forall x \ in \ {0,1 \} ^ {*}, M_ {w} (w)= x \} $ является разрешенным.

Прежде всего: я не понимаю, почему мы можем использовать теорему Риса в первую очередь: если бы я выбрал две TurgingMachines $ m_ {w} $ и $ m_ {w '} $ с $ w \ Neq w' $ Тогда я бы получил $ m_ {w} (w)= m_ {w '} (w)= x $ . Но это приведет к $ w '$ не находясь в $ l_ {5} $ и <класс span= «Математический контейнер»> $ W \ in l_ {5} $ . Или я что-то не понимаю?

Второе: решение говорит, что язык $ l_ {5} $ разрешен, как $ l_ {5}=emptyset $ потому, что вывод четко определен с фиксированным входом. Но почему так? Я думал, что $ l_ {5} $ не пусто, потому что есть TM, который выводится X на своем собственном входе, и есть некоторые, которые нет.

Answer 1

Слово $ W $ относится к $ l_5 $ Если для всех $ x \ in \ {0,1 \} ^ * $ Это тот случай, когда $ m_w (w)= x $ .В частности, если $ W \ in l_5 $ затем $ m_w (w)= 0 $ и $ m_w (w)= 1 $ , который не может быть правдой.Таким образом, ни одно слово не относится к $ l_5 $ .