76
правок
Изменения
Нет описания правки
<!--Понятно, что <tex>DSPACE(f(n)) \subseteq DSPACE(g(n))</tex>, поскольку программа, ограниченная по памяти функцией <tex>f</tex>, проходит ограничение <tex>g</tex>.<br /> -->
Для доказательства воспользуемся диагональным методом.
<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> иногда называют диагональными, поскольку для неотрицательных <tex>x</tex> находятся на диагонали таблицы функция — аргумент.
<br/><tex>
\begin{pmatrix}
