53
правки
Изменения
Нет описания правки
Пусть <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>.
