Временная и пространственная сложность алгоритмов/Задачи/ex-limited-halt — различия между версиями

<latex>

<latex>

Рассмотрим язык $L$ состоящий из слов $\langle M,x,t \rangle$, для которых ДМТ \MT{M} останавливается на $x$ не позже, чем через $t$ шагов.

Рассмотрим язык $L$ состоящий из слов $\langle M,x,t \rangle$, для которых ДМТ \MT{M} останавливается на $x$ не позже, чем через $t$ шагов.

Докажите: $L \in EXPTIME$.

Докажите: $L \in EXPTIME$.

</latex>

</latex>

<!--Вообще-то, решения уже есть-->

<!--Вообще-то, решения уже есть-->