Изменения

Рассмотрим язык <mathtex>L = \{ <\langle m,x> \rangle \mid m(<\langle m,x>\rangle)</mathtex> не допускает, работая не более <mathtex> f(|<\langle m,x>\rangle |)\,\!</mathtex> времени <mathtex>\}\,\!</mathtex> .

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

Рассмотрим <mathtex>m_0(<\langle m_0,x>\rangle )\,\!</mathtex>.

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

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

Следовательно такой машины не существует. Таким образом, <mathtex>L \notin DTIME(f)</mathtex>.

<mathtex>L \in DTIME(g)</mathtex>, так как можно просимулировать . Возьмеме такую машину Тьюринга <mathtex>m_1\,\!</mathtex> такую, что которой дается на вход пара <math>L(m_1)=L\<m_2,x> \!in L</math>. Для каждой пары и она симулирует нужное количество шагов машины <mathtex><m_2\,x> \in L!</mathtex> рассмотрим на входе <mathtex>m_2(<m_2,x>)\,\!</mathtex>. Если <mathtex>m_2\,\!</mathtex> завершила работу и не допустила, то <mathtex>m_1\,\!</mathtex> допускает <mathtex><m_2,x>\,\!</mathtex>. В другом случае не допускает. Так как любая такая машина работает не более <math>f(|<m_2,x>|)\,\!</math> времени, а <math> \lim_{n \rightarrow \infty} t(f(n))/g(n) = 0</math>, <mathtex>m_1\,\!</mathtex> будет работать не более <mathtex>g(|<m_2,x>|)\,\!</mathtex> времени.

Получается, что <mathtex>L \in DTIME(g(n)) \setminus DTIME(f(n))</mathtex> и <mathtex>L \neq \empty</mathtex>. Следовательно, <mathtex>DTIME(g(n)) \neq DTIME(f(n))</mathtex>