53
правки
Изменения
Нет описания правки
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.
Рассмотрим язык <math>L = \{ <\langle m,x> \rangle \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)\,\!</math> памяти <math>\}\,\!</math> .
Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина Тьюринга <math>m_0\,\!</math> такая, что <math>L(m_0)=L\,\!</math>.
