23
правки
Изменения
→Доказательство
Рассмотрим <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> памяти. Получаем противоречие.
