83
правки
Изменения
→Доказательство
Зафиксируем <tex>f</tex> и <tex>g</tex>.
Рассмотрим язык <tex>L = \{ \langle m,x\rangle \mid m(\langle m,x\randlerangle )</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex> .
Пусть <tex>L \in DSPACE(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L</tex>.
Пусть <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>. Тогда <tex>\langle m_0,x\rangle \in L</tex>, но в <tex>L</tex> по определению не может быть пары <tex>\langle m,x\rangle</tex>, которую допускает <tex>m</tex>. Таким образом, получаем противоречие.
Если <tex>m_0</tex> не допускает <tex><\langle m_0,x>\rangle</tex>, то <tex>\langle m_0,x\rangle</tex> не принадлежит языку <tex>L</tex>. Это значит, что либо <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>, либо не допускает, используя памяти больше <tex>f(|<\langle m_0,x>\rangle|)</tex>. Но <tex>m_0</tex> выбрана таким образом, что на любом входе <tex>x</tex> она использует не более <tex>f(|x|)</tex> памяти. Получаем противоречие.
Следовательно, такой машины не существует. Таким образом, <tex>L \notin DSPACE(f)</tex>.
