Теорема о временной иерархии
Формулировка
Теорема о временной иерархии утверждает, что для любых двух конструируемых по времени функций и таких, что , выполняется .
Доказательство
Зафиксируем
и .Рассмотрим язык
не допускает, работая не более времени .Пусть
, тогда для него есть машина Тьюринга такая, что .Рассмотрим
.Пусть
допускает . Тогда , в силу определения . Но в по определению не может быть пары , которую допускает , так как . Таким образом, получаем противоречие.Если
не допускает , то не принадлежит языку . Это значит, что либо допускает , либо не допускает, работая больше времени . Но , поэтому на любом входе работает не более времени. Получаем противоречие.Следовательно такой машины не существует. Таким образом,
., так как можно просимулировать машину Тьюринга такую, что . Для каждой пары рассмотрим . Если завершила работу и не допустила, то допускает . В другом случае не допускает. Так как любая такая машина работает не более времени, а , будет работать не более времени.
Получается, что и . Следовательно,
Теорема доказана.