Обсуждение:Теорема о ёмкостной иерархии

Материал из Викиконспекты
Перейти к: навигация, поиск

"Любая такая машина использует памяти не более [math]f(|\langle m_1,x\rangle|)[/math]."

Отсюда следует, что построенная машина принадлежит классу DSPACE(f), что неверно. Кажется, должно быть что-то типа + константа в вышеприведенном утверждении.