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> иногда называют диагональными, поскольку находятся на диагонали таблицы «функция — аргумент».
<br/>
{| class="wikitable" align="centre"
|about=о временной иерархии
|id=time
|statement=Пусть даны две функции <tex>f</tex> и <tex>g</tex> такие, <span title="Здесь Sim(n) — время симуляции n шагов одной машины Тьюринга на другой машине" style="border-bottom: 1px dotted; cursor: help;">что</span> <tex>\lim \limits_{n\rightarrow\infty} \frac{Sim(f(n))}{g(n)}=0</tex>, тогда где <tex>Sim(n)</tex> — время симуляции <tex>n</tex> шагов одной машины Тьюринга на другой машине. Тогда <tex>DTIME(f(n)) \neq DTIME(g(n))</tex>.
|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]]. При этом в отличии от памяти, время работы машины Тьюринга меньше, чем время ее симуляции на другой машине, из-за чего на соотношение <tex>f</tex> и <tex>g</tex> поставлено более сильное условие.
Положим <tex>h(n)=Sim^{-1}(g(n))</tex>, где <tex>Sim^{-1}</tex> — обратная к времени симуляции функция, <tex>L=\{x\bigm|x(x)\Bigr|_{T\leq h(|x|)}\neq 1\}</tex>. Тогда:
