Изменения

Рассмотрим <math>m_0(<m_0,x>)</math>. <math>m_0</math> не может допускать <math><m_0,x></math> в силу определения. Если бы она допускала, то <math><m_0,x> \in L</math>. Получили противоречие. Если <math>m_0</math> не допускает <math><m_0,x></math>, то она допускает, используя больше памяти. Следовательно такой машины не существует.

Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math>.

Теорема доказана.