Изменения

Зафиксируем <mathtex>f\,\!</mathtex> и <mathtex>g\,\!</mathtex>.

Рассмотрим язык <mathtex>L = \{ \langle m,x\rangle \mid m(<\langle m,x>\randle)</mathtex> не допускает, используя не более <mathtex> f(|<\langle m,x>\rangle|)\,\!</mathtex> памяти <mathtex>\}\,\!</mathtex> .

Пусть <mathtex>L \in DSPACE(f)</mathtex>, тогда для него есть машина Тьюринга <mathtex>m_0\,\!</mathtex> такая, что <mathtex>L(m_0)=L\,\!</mathtex>.

Рассмотрим <mathtex>m_0(<\langle m_0,x>\rangle)\,\!</mathtex>.

Пусть <mathtex>m_0\,\!</mathtex> допускает <mathtex><\langle m_0,x>\,\!rangle</mathtex>. Тогда <mathtex><\langle m_0,x> \rangle \in L</mathtex>, но в <mathtex>L\,\!</mathtex> по определению не может быть пары <mathtex><\langle m,x>\,\!rangle</mathtex>, которую допускает <mathtex>m\,\!</mathtex>. Таким образом, получаем противоречие.

Если <mathtex>m_0\,\!</mathtex> не допускает <mathtex><m_0,x>\,\!</mathtex>, то <mathtex><\langle m_0,x>\,\!rangle</mathtex> не принадлежит языку <mathtex>L\,\!</mathtex>. Это значит, что либо <mathtex>m_0\,\!</mathtex> допускает <mathtex><\langle m_0,x>\,\!rangle</mathtex>, либо не допускает, используя памяти больше <mathtex>f(|<m_0,x>|)\,\!</mathtex>. Но <mathtex>m_0\,\!</mathtex> выбрана таким образом, что на любом входе <mathtex>x\,\!</mathtex> она использует не более <mathtex>f(|x|)\,\!</mathtex> памяти. Получаем противоречие.

Следовательно , такой машины не существует. Таким образом, <mathtex>L \notin DSPACE(f)</mathtex>.

<math>L \in DSPACE(g)</math>, так как можно проэмулировать машину Тьюринга <math>m_1\,\!</math> такую, что <math>L(m_1)=L\,\!</math>. Для каждой пары <math><m_3,x> \in L</math> рассмотрим <math>m_3(<m_3,x>)\,\!</math>. Если <math>m_3\,\!</math> завершила работу и не допустила, то <math>m_1\,\!</math> допускает <math><m_3,x>\,\!</math>. В другом случае не допускает. Так как любая такая машина использует памяти не более <math>f(|<m_3,x>|)\,\!</math>, а <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, <math>m_1\,\!</math> будет использовать памяти не более <math>g(|<m_3,x>|)\,\!</math>.

Получается, что <mathtex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</mathtex> и <mathtex>L \neq \empty</mathtex>. Следовательно, <mathtex>DSPACE(g(n)) \neq DSPACE(f(n))</mathtex>