Теорема о ёмкостной иерархии — различия между версиями
Mashuna (обсуждение | вклад) (→Доказательство) |
Mashuna (обсуждение | вклад) (→Доказательство) |
||
| Строка 3: | Строка 3: | ||
== Доказательство == | == Доказательство == | ||
| − | Зафиксируем <math>f</math> и <math>g</math>. | + | Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>. |
| − | Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)</math> памяти <math>\}</math> . | + | Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)\,\!</math> памяти <math>\}\,\!</math> . |
| − | Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина | + | Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина Тьюринга <math>m_0\,\!</math> такая, что <math>L(m_0)=L\,\!</math>. |
| − | Рассмотрим <math>m_0(<m_0,x>)</math>. | + | Рассмотрим <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> \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>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>. | Следовательно такой машины не существует. Таким образом, <math>L \notin DSPACE(f)</math>. | ||
| − | <math>L \in DSPACE(g)</math>, так как можно проэмулировать <math> | + | <math>L \in DSPACE(g)</math>, так как можно проэмулировать машину Тьюринга <math>m_1\,\!</math> такую, что <math>L(m_1)=L\,\!</math>. Для каждой пары <math><m_3,x> \in L</math> рассмотрим <math>m_3(<m_3,x>)\,\!</math>. Если <math>m_3\,\!</math> завершила работу и не допустила, то <math>m_1\,\!</math> допускает <math><m_3,x>\,\!</math>. В другом случае не допускает. Так как любая такая машина использует памяти не более <math>f(|<m_3,x>|)\,\!</math>, а <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, <math>m_1\,\!</math> будет использовать памяти не более <math>g(|<m_3,x>|)\,\!</math>. |
| − | Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math>. | + | |
| + | Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math> и <math>L \neq \empty</math>. Следовательно, <math>DSPACE(g(n)) \neq DSPACE(f(n))</math> | ||
Теорема доказана. | Теорема доказана. | ||
Версия 23:55, 12 марта 2010
Формулировка
Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций и таких, что , выполняется .
Доказательство
Зафиксируем и .
Рассмотрим язык не допускает, используя не более памяти .
Пусть , тогда для него есть машина Тьюринга такая, что .
Рассмотрим .
Пусть допускает . Тогда , но в по определению не может быть пары , которую допускает . Таким образом, получаем противоречие.
Если не допускает , то не принадлежит языку . Это значит, что либо допускает , либо не допускает, используя памяти больше . Но , поэтому на любом входе использует не более памяти. Получаем противоречие.
Следовательно такой машины не существует. Таким образом, .
, так как можно проэмулировать машину Тьюринга такую, что . Для каждой пары рассмотрим . Если завершила работу и не допустила, то допускает . В другом случае не допускает. Так как любая такая машина использует памяти не более , а , будет использовать памяти не более .
Получается, что и . Следовательно,
Теорема доказана.
