23
правки
Изменения
→Формулировка
== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <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 = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math>f(<m,x>)</math> памяти <math>\}</math> .
Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина тьюринга <math>m_0</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>m_0</math> не допускает <math><m_0,x></math>, то она допускает, используя больше памяти. Следовательно такой машины не существует.
<math>L \in DSPACE(g)</math> так как можно проэмулировать <math>m</math>.
Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math>.
Теорема доказана.
