Формулировка
Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [math]f\,\![/math] и [math]g\,\![/math] таких, что [math] \lim_{n \rightarrow \infty} f(n)/g(n) = 0[/math], выполняется [math]DSPACE(g(n)) \ne DSPACE(f(n))[/math].
Доказательство
Зафиксируем [math]f\,\![/math] и [math]g\,\![/math].
Рассмотрим язык [math]L = \{ \lt m,x\gt \mid m(\lt m,x\gt )[/math] не допускает, используя не более [math] f(|\lt m,x\gt |)\,\![/math] памяти [math]\}\,\![/math] .
Пусть [math]L \in DSPACE(f)[/math], тогда для него есть машина Тьюринга [math]m_0\,\![/math] такая, что [math]L(m_0)=L\,\![/math].
Рассмотрим [math]m_0(\lt m_0,x\gt )\,\![/math].
Пусть [math]m_0\,\![/math] допускает [math]\lt m_0,x\gt \,\![/math]. Тогда [math]\lt m_0,x\gt \in L[/math], но в [math]L\,\![/math] по определению не может быть пары [math]\lt m,x\gt \,\![/math], которую допускает [math]m\,\![/math]. Таким образом, получаем противоречие.
Если [math]m_0\,\![/math] не допускает [math]\lt m_0,x\gt \,\![/math], то [math]\lt m_0,x\gt \,\![/math] не принадлежит языку [math]L\,\![/math]. Это значит, что либо [math]m_0\,\![/math] допускает [math]\lt m_0,x\gt \,\![/math], либо не допускает, используя памяти больше [math]f(|\lt m_0,x\gt |)\,\![/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 \in DSPACE(g)[/math], так как можно проэмулировать машину Тьюринга [math]m_1\,\![/math] такую, что [math]L(m_1)=L\,\![/math]. Для каждой пары [math]\lt m_3,x\gt \in L[/math] рассмотрим [math]m_3(\lt m_3,x\gt )\,\![/math]. Если [math]m_3\,\![/math] завершила работу и не допустила, то [math]m_1\,\![/math] допускает [math]\lt m_3,x\gt \,\![/math]. В другом случае не допускает. Так как любая такая машина использует памяти не более [math]f(|\lt m_3,x\gt |)\,\![/math], а [math] \lim_{n \rightarrow \infty} f(n)/g(n) = 0[/math], [math]m_1\,\![/math] будет использовать памяти не более [math]g(|\lt m_3,x\gt |)\,\![/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]
Теорема доказана.
