Изменения

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

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

Пусть Рассмотрим язык <mathtex>L = \{ \langle m,x \in DTIMErangle \mid m(f\langle m,x \rangle)</mathtex>не допускает, тогда для него есть машина Тьюринга работая не более <mathtex>m_0f(| \langle m,x \rangle |)\,\!</mathtex> такая, что времени <mathtex>L(m_0)=L\}\,\!</mathtex>.

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

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

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

Следовательно такой машины Если <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>. Но <mathtex>L \notin in DTIME(f)</mathtex>, поэтому <tex>m_0</tex> на любом входе <tex>x</tex> работает не более <tex>f(|x|)</tex> времени. Получаем противоречие.

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

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