Изменения
Новая страница: «"Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>." Отсюда следует, что п…»
"Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>."
Отсюда следует, что построенная машина принадлежит классу DTIME(f), что неверно. Кажется, должно быть что-то типа + константа в вышеприведенном утверждении.
Отсюда следует, что построенная машина принадлежит классу DTIME(f), что неверно. Кажется, должно быть что-то типа + константа в вышеприведенном утверждении.
