Изменения

Перейти к: навигация, поиск

Теорема о ёмкостной иерархии

544 байта добавлено, 23:51, 31 января 2019
м
Дмитрий Мурзин переименовал страницу Теорема о емкостной иерархии в Теорема о ёмкостной иерархии: Ёфикация
== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <mathtex>f\,\!</mathtex> и <mathtex>g\,\!</mathtex> таких, что <mathtex> \lim_lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</mathtex>, выполняется <math>'''DSPACE'''(''g''(''n'')) \&ne ; '''DSPACE'''(''f''(''n''))</math>.
== Доказательство ==
Зафиксируем функции <mathtex>f\,\!</mathtex> и <mathtex>g\,\!</mathtex>.
Рассмотрим язык <mathtex>L = \{ <\langle m,x> \rangle \mid m(<\langle m,x>\rangle )</mathtex> не допускает, используя не более <mathtex> f(|<\langle m,x>\rangle|)\,\!</mathtex> памяти <mathtex>\}</tex> и докажем, что <tex>L \,notin DSPACE(f)</tex> и <tex>L \!in DSPACE(g)</mathtex> .
Пусть Допустим, что <mathtex>L \in DSPACE(f)</mathtex>, тогда для него есть существует детерминированная машина Тьюринга <mathtex>m_0\,\!</mathtex> такая, что <mathtex>L(m_0)=L\,\!</mathtex>.
Рассмотрим выход машины <mathtex>m_0(</tex> на входе <tex>\langle m_0,x>)\,\!rangle</mathtex>.
Пусть <mathtex>m_0\,\!</mathtex> допускает <mathtex><\langle m_0,x>\,\!rangle</mathtex>. Тогда <mathtex><\langle m_0,x> \rangle \in L</mathtex>, но в <mathtex>L\,\!</mathtex> по определению не может быть пары <mathtex><\langle m,x>\,\!rangle</mathtex>, которую допускает <mathtex>m\,\!</mathtex>. Таким образом, получаем противоречие<tex>m_0</tex> не может допускать <tex>\langle m_0,x\rangle</tex>.
Если <mathtex>m_0\,\!</mathtex> не допускает <mathtex><\langle m_0,x>\,\!rangle</mathtex>, то <mathtex><\langle m_0,x>\,\!rangle</mathtex> не принадлежит языку <mathtex>L\,\!</mathtex>. Это Из определения это значит, что либо <mathtex>m_0\,\!</mathtex> допускает <mathtex><\langle m_0,x>\,\!rangle</mathtex>, либо не допускает, используя памяти больше <mathtex>f(|<\langle m_0,x>\rangle|)\,\!</mathtex>. Но <mathtex>L \in DSPACE(f)m_0</mathtex>выбрана таким образом, поэтому <math>m_0\,\!</math> что на любом входе <mathtex>x\,\!</mathtex> она использует не более <mathtex>f(|x|)\,\!</mathtex> памяти. Получаем противоречие.
Следовательно , такой машины не существует. Таким образом, <mathtex>L \notin DSPACE(f)</mathtex>.
<mathtex>L \in DSPACE(g)</mathtex>, так как языку <tex>L</tex> можно проэмулировать сопоставить машину Тьюринга <mathtex>m_1\,\!m_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_1</tex> завершила работу, используя не более <tex>m_3f(|\langle m_1,x\!rangle|)</mathtex> завершила работу памяти, и не допустила, то <mathtex>m_1\,\!m_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>, поэтому начиная с некоторого <tex>n</tex>, <mathtex>m_1\,\!</mathtex> будет использовать памяти не более <mathtex>g(|<m_3\langle m_1,x>\rangle|)\,\!</mathtex>.
 ПолучаетсяТаким образом получили, что <mathtex>L \in DSPACE(g(n)) \ setminus DSPACE(f(n))</math> и <math>L \neq \empty</mathtex>. Следовательно, <mathtex>DSPACE(g(n)) \neq DSPACE(f(n))</mathtexТеорема доказана, что и требовалось доказать.

Навигация