Упражнения

Покажите, что $E Q_{\text{CFG }}$ неразрешим.

Покажите, что $E Q_{\mathrm{CFG}}$ ко-распознаваем.

Найдите соответствие в следующем экземпляре проблемы соответствий Поста.

Если $A \leq_{\mathrm{m}} B$, а $B$ — регулярный язык, следует ли отсюда, что $A$ — регулярный язык? Почему да или почему нет?

Покажите, что $A_{\mathrm{TM}}$ не сводится к $E_{\mathrm{TM}}$. Иными словами, покажите, что не существует вычислимой функции, сводящей $A_{\text{TM }}$ к $E_{\text{TM }}$. (Подсказка: используйте доказательство от противного и уже известные вам факты об $A_{\text{TM }}$ и $E_{\text{TM }}$.)

Покажите, что $\leq_{\mathrm{m}}$ является транзитивным отношением.

Покажите, что если $A$ распознаётся машиной Тьюринга и $A \leq_{\mathrm{m}} \bar{A}$, то $A$ разрешим.

В доказательстве теоремы 5.15 мы изменили машину Тьюринга $M$ так, чтобы она никогда не пыталась сдвинуть головку за левый край ленты. Предположим, что мы не внесли это изменение в $M$. Измените построение PCP, чтобы обработать этот случай.