Изменения

'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется <tex>'''DSPACE'''(''g''(''n'')) \&ne ; '''DSPACE'''(''f''(''n''))</tex>.

Зафиксируем функции <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 \notin DSPACE(f)</tex> и <tex>L \in DSPACE(g)</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>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>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> памяти. Получаем противоречие.

<mathtex>L \in DSPACE(g)</mathtex>, так как языку <tex>L</tex> можно проэмулировать сопоставить машину Тьюринга <mathtex>m_1m_0</mathtex> такую, что распознающую <mathtex>L(m_1)=L</mathtex>. Для каждой пары и такую, что на любом входе <mathtex><m_3\langle m_1,x> \rangle \in L</mathtex> рассмотрим <mathtex>m_3(m_0</tex> будет работать аналогично <m_3,xtex>)\,\!m_1</mathtex>. Если <mathtex>m_3m_1</mathtex> завершила работу , используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <mathtex>m_1m_0</mathtex> допускает <mathtex><m_3\langle m_1,x>\rangle</mathtex>. В другом случае не допускает. Так как любая Любая такая машина использует памяти не более <mathtex>f(|<m_3\langle m_1,x>\rangle|)</mathtex>, а . По условию теоремы <mathtex> \lim_lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</mathtex>, поэтому начиная с некоторого <mathtex>n</tex>, <tex>m_1</mathtex> будет использовать памяти не более <mathtex>g(|<m_3\langle m_1,x>\rangle|)</mathtex>.

 ПолучаетсяТаким образом получили, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex> и <tex>L \neq \empty</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex> Теорема доказана, что и требовалось доказать.