Определение, является ли следующий язык разрешимым

Question

{⟨M, N⟩ |Все строки в L (M) ∩L (N) начинаются с 110.}

Я думаю, что этот язык разрешим.Мы можем изготовить машину Тьюринга ТМ, которая принимает в качестве входных данных.Для каждой строки из L (M) ∩L (N), если строка начинается с 110, после первых 3 цифр мы останавливаемся и принимаем.Если первые три цифры не равны 110, мы останавливаемся и отклоняем.Я не уверен, что мы делаем, если строка не в L (M) ∩L (N).

Также в целом я не уверен, работает ли моя машина Тьюринга на самом деле или нет.Могу ли я получить отзыв по этому поводу?

Answer 1

Если M и N - машины Тьюринга, этот язык не может быть разрешен. Если бы это было так, мы могли бы сделать N ТМ, который принимает все строки, и тогда у нас был бы решатель для {M | все строки в M начинаются с 110}. Мы можем признать, что это не разрешимо, поскольку условие является истинным для некоторых ТМ, ложным для других, и оно семантическое в том смысле, что оно имеет дело со строками в языке; поэтому применима теорема Райс.