Изменения

'''Теорема о временной иерархии''' утверждает, что для Пусть можно просимулировать <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</tex>, выполняется '''DTIME'''(''g''(''n'')) &ne; '''DTIME'''(''f''(''n'')). == Доказательство ==Зафиксируем <tex>f</tex> и <tex>g</tex>. Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m( \langle m,x \rangle)</tex> не допускает, работая не более <tex> f(| \langle m,x \rangle |)\,\!</tex> времени <tex>\}\,\!</tex> . Пусть <tex>L \in DTIME(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0) =L\,\!</tex>. Рассмотрим <tex>m_0( \langle m_0,x \rangle )\,\!</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</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 \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</mathtex>.  Получается, что <tex>L \in DTIME(g(n)) \setminus DTIME(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, выполняется <mathtex>DTIME(g(n)) \ne neq DTIME(f(n))</mathtex> Теорема доказана.