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