Изменения
→Доказательство
Зафиксируем функции <tex>f</tex> и <tex>g</tex>.
Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex> и докажем, что <tex>L \notin DSPACE(f)</tex> и <tex>L \in DSPACE(g)</tex>.
Допустим, что <tex>L \in DSPACE(f)</tex>, тогда существует детерминированная машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L</tex>.
<tex>L \in DSPACE(g)</tex>, так как языку <tex>L</tex> можно сопоставить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex> и такую, что на любом входе <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <tex>m_0</tex> допускает <tex>\langle m_1,x\rangle</tex>. В другом случае не допускает. Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>. <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, поэтому начиная с некоторого <tex>n</tex>, <tex>m_1</tex> будет использовать памяти не более <tex>g(|\langle m_1,x\rangle|)</tex>.
