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

Формулировка

Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций $f$ и $g$ таких, что $\lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0$, выполняется DSPACE(g(n)) ≠ DSPACE(f(n)).

Доказательство

Зафиксируем функции $f$ и $g$.

Рассмотрим язык $L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )$ не допускает, используя не более $f(|\langle m,x\rangle|)$ памяти $\}$ и докажем, что $L \notin DSPACE(f)$ и $L \in DSPACE(g)$.

Допустим, что $L \in DSPACE(f)$, тогда существует детерминированная машина Тьюринга $m_0$ такая, что $L(m_0)=L$.

Рассмотрим выход машины $m_0$ на входе $\langle m_0,x\rangle$.

Пусть $m_0$ допускает $\langle m_0,x\rangle$. Тогда $\langle m_0,x\rangle \in L$, но в $L$ по определению не может быть пары $\langle m,x\rangle$, которую допускает $m$. Таким образом, $m_0$ не может допускать $\langle m_0,x\rangle$.

Если $m_0$ не допускает $\langle m_0,x\rangle$, то $\langle m_0,x\rangle$ не принадлежит языку $L$. Из определения это значит, что либо $m_0$ допускает $\langle m_0,x\rangle$, либо не допускает, используя памяти больше $f(|\langle m_0,x\rangle|)$. Но $m_0$ выбрана таким образом, что на любом входе $x$ она использует не более $f(|x|)$ памяти. Получаем противоречие.

Следовательно, такой машины не существует. Таким образом, $L \notin DSPACE(f)$.

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

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