Изменения

Зафиксируем <tex>f\,\!</tex> и <tex>g\,\!</tex>.

Пусть <tex>L \in DTIME(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0\,\!</tex> такая, что <tex>L(m_0)=L\,\!</tex>.

Пусть <tex>m_0\,\!</tex> допускает <tex> \langle m_0,x \rangle \,\!</tex>. Тогда <tex> \langle m_0,x \rangle \in L</tex>, в силу определения <tex>m_0\,\!</tex>. Но в <tex>L</tex> по определению не может быть пары <tex> \langle m_0,x \rangle \,\!</tex>, которую допускает <tex>m_0\,\!</tex>, так как <tex>m_0 \in DTIME(f)</tex>. Таким образом, получаем противоречие.

Если <tex>m_0\,\!</tex> не допускает <tex> \langle m_0,x \rangle \,\!</tex>, то <tex> \langle m_0,x \rangle ,\!</tex> не принадлежит языку <tex>L\,\!</tex>. Это значит, что либо <tex>m_0\,\!</tex> допускает <tex> \langle m_0,x \rangle \,\!</tex>, либо не допускает, работая больше времени <tex>f(| \langle m_0,x \rangle |)\,\!</tex>. Но <tex>L \in DTIME(f)</tex>, поэтому <tex>m_0\,\!</tex> на любом входе <tex>x\,\!</tex> работает не более <tex>f(|x|)\,\!</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> по условию.