Изменения

<ref>Суть данного метода для набора множеств <tex>\{A_x\}</tex> заключается в построении нового множества <tex>B</tex> по принципу: <tex>x \in B \Leftrightarrow x \notin A_x</tex>. В этом случае <tex>A_x \neq B</tex> для любого <tex>x</tex>. Аналогичный прием можно применять для набора функций <tex>\{f_i\}</tex> путем построения новой функции <tex>f':f'(x) \neq f_x(x)</tex>. Элементы <tex>f_x(x)</tex> иногда называют диагональными, поскольку находятся на диагонали таблицы функция «функция — аргументаргумент».<br/>{| class="wikitable" align="centre"|-| ||<tex>\begin{pmatrix}& 0 & </tex>||<tex>1 & </tex>||<tex>\cdots \\</tex>|-|<tex>f_0 & </tex>||<tex>\mathbf{f_0(0)} & </tex>||<tex>f_0(1) & </tex>||<tex>\cdots \\</tex>|-|<tex>f_1 & </tex>||<tex>f_1(0) & </tex>||<tex>\mathbf{f_1(1)} & </tex>||<tex>\cdots \\ </tex>|-|<tex>\vdots & </tex>||<tex>\vdots & </tex>||<tex>\vdots & </tex>||<tex>\ddots \\\end{pmatrix}</tex>|-|}

Рассмотрим функцию <tex>h(n)=\sqrt{f(n)g(n)}</tex> и язык <tex>L=\{x\bigm|x(x)\Bigr|_{S\leq h(|x|)}\neq 1\}</tex>, где запись <tex>S\leq h(|x|)</tex> означает, что программа запускается с лимитом памяти <tex>h(|x|)</tex>. Иначе говоря, <tex>L</tex> — это язык программ, которые не допускают собственный код, используя не более <tex>h(|x|)</tex> памяти. <br/>Докажем, что <tex>L\in DSPACE(g(n))\setminus DSPACE(f(n))</tex>.<br/><br/>Так как <tex>h(n)=o(g(n))</tex>, то понятно, что * <tex>L \in DSPACE(g(n))</tex>. Действительно, для проверки принадлежности программы <tex>x</tex> языку достаточно запустить её с лимитом памяти <tex>h(|x|)</tex> и проверить, что результат не равен 1. Тогда вся проверка будет выполнена с использованием не более <tex>g(|x|)</tex> памяти в силу накладываемых ограничений.<ref>Вообще говоря, для корректного запуска с лимитом по памяти на функцию <tex>h</tex> дополнительно накладывается условие конструируемости по памяти, т. е. то есть возможность вычислить значение функции по <tex>x</tex>, используя не более <tex>h(x)</tex> памяти, однако часто это условие опускается.</ref><br /><br/>Предположим теперь, что * <tex>L \in notin DSPACE(f(n))</tex>. Тогда Пусть это не так, тогда существует программа <tex>p</tex>, распознающая язык <tex>L</tex> и использующая не более <tex>c \cdot f(n)</tex> памяти. Так как <tex>f(n)=o(h(n))</tex>, то <tex>\exists n_0: \forall n>n_0 \Rightarrow c\cdot f(n)<h(n)</tex>. Будем считать, что <tex>|p|>n_0</tex> (иначе добавим в программу пустые строки, искусственно увеличив её длину), тогда при вызове <tex>p(p)</tex> потребуется не более <tex>h(|p|)</tex> памяти. Выясним, принадлежит ли <tex>p</tex> языку <tex>L</tex>. Допустим, что <tex>p\in L</tex>, тогда <tex>p(p)=1</tex>, значит, <tex>p\notin L</tex> по определению языка <tex>L</tex>. Пусть теперь <tex>p\notin L</tex>. Но тогда <tex>p(p) \ne 1</tex>, следовательно, <tex>p\in L</tex>.

|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]]. При этом в отличии от памяти, время работы машины Тьюринга меньше, чем время ее симуляции на другой машине, из-за чего на соотношение <tex>f</tex> и <tex>g</tex> поставлено более сильное условие.Положим <tex>h(n)=Sim^{-1}(\frac{f(n)g(n)}{Sim(f(n))}), L=\{x\bigm|x(x)\Bigr|_{T\leq h(|x|)}\neq 1\}</tex>. Заметим, что <tex>Sim(h(n))=o(g(n))</tex> и <tex>f(n)=o(h(n))</tex>. Тогда:* <tex>L \in DTIME(g(n))</tex>, поскольку запуск с ограничением <tex>T \leq h(|x|)</tex> осуществляется за <tex>O(g(n))</tex> времени;* <tex>L \notin DTIME(f(n))</tex> (доказывается аналогично соответствующему пункту предыдущей теоремы).

=== Замечания Примечания ===