Изменения
→Доказательство
== Доказательство ==
Зафиксируем <mathtex>f\,\!</mathtex> и <mathtex>g\,\!</mathtex>.
Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m( \langle m,x \rangle)</tex> не допускает, работая не более <tex> f(| \langle m,x \rangle |)\,\!</tex> времени <tex>\}\,\!</tex> .
Следовательно такой машины не существует. Таким образом, <tex>L \notin DTIME(f)</tex>.
<tex>L \in DTIME(g)</tex>. Возьмеме такую машину Тьюринга <tex>m_1\,\!</tex>, которой дается на вход пара <tex> \langle m_2,x \rangle \in L</tex> и она симулирует нужное количество <tex>f(| \langle m_2,x \rangle |)\,\!</tex> шагов машины <tex>m_2\,\!</tex> на входе <tex>x\,\!</tex>. Если <tex>m_2\,\!</tex> завершила работу и не допустила, то <tex>m_1\,\!</tex> допускает <tex> \langle m_2,x \rangle \,\!</tex>. В другом случае не допускает. <tex>L(m_1) = L</tex> и <tex>m_1</tex> будет работать не более <tex>g(| \langle m_2,x \rangle |)\,\!</tex> времени, так как <tex> \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0</tex> по условию.
Получается, что <tex>L \in DTIME(g(n)) \setminus DTIME(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, <tex>DTIME(g(n)) \neq DTIME(f(n))</tex>
Теорема доказана.
