L = {T | T - машина Тьюринга, которая распознает {00, 01}} Доказательство L неразрешимо

Question

L = { | T - машина Тьюринга, которая распознает {00, 01}}

Докажи, что L неразрешима.

У меня действительно есть трудности, даже понимание сокращения, чтобы использовать здесь.

Я не прошу бесплатный обед, просто толчок в правильном направлении.

Answer 1

Прямое применение теоремы Райс позволит вам доказать это, не делая никакой работы вообще.

Некоторые машины Тьюринга распознают {00, 01}. Некоторые нет. Различие семантическое в том, что оно связано с принятыми строками, а не со структурой автомата. Следовательно, по теореме Райс это множество неразрешимо.