53
правки
Изменения
Нет описания правки
Пусть можно просимулировать <tex>n</tex> шагов машины Тюринга на другой машине Тьюринга за время <tex>t(n)</tex>.
Для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <tex>f\,\!</tex> и <tex>g\,\!</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} \frac{t(f(n))/}{g(n) } = 0</tex>, выполняется <tex>DTIME(g(n)) \ne DTIME(f(n))</tex>.
== Доказательство ==
