Изменения

Рассмотрим язык <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> такая, что <math>L(m_0)=L</math>.

Рассмотрим <math>m_0(<m_0,x>)</math>.  Пусть <math>m_0</math> не может допускать допускает <math><m_0,x></math> в силу определения. Если бы она допускала, то Тогда <math><m_0,x> \in L</math>, но в <math>L</math> по определению не может быть пары <math><m,x></math>, которую допускает <math>m</math>. Получили Таким образом, получаем противоречие.  Если <math>m_0</math> не допускает <math><m_0,x></math>, то она <math><m_0,x></math> не принадлежит языку <math>L</math>. Это значит, что либо <math>m_0</math> допускает <math><m_0,x></math>, либо не допускает, используя памяти больше <math>f(|<m_0,x>|)</math>. Но <math>L \in DSPACE(f)</math>, поэтому <math>m_0</math> на любом входе <math>x</math> использует не более <math>f(|x|)</math> памяти. Получаем противоречие.  Следовательно такой машины не существует. Таким образом, <math>L \notin DSPACE(f)</math>.