Формально об алгоритмах. Вычислительные модели/Задачи/ex-turing-max-time-grows — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 11 промежуточных версий этого же участника)
Строка 7: Строка 7:
 
</latex>
 
</latex>
  
Для любой b(n) - вычислимой и всюду определенной функции
 
и некоторого n (выберем n большим) существует MT с n состояниями n символами, которая при запуске на пустом входе 2^n раз вычисляет
 
значение b(n), записывая его на ленту в единичной системе счисления, и затем останавливается.
 
При этом она сделает b(n) * 2^n шагов до остановке.
 
А значит T(n)/b(n) > 2^n / b(n) = 2^n -> к бесконечности при стремлении n в бесконечность.
 
  
Тем самым мы доказали утверждения для машины конкретной конфигурации машины тьюринга. Значит и для любой машины с бОльшим временем исполнения
 
этот факт останется справедлив => утверждение верно и для маишны с максимальным временем работы.
 
 
Утверждение доказано.
 
[[Category:На проверку]]
 
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
 +
 +
[[Категория:Решенные задачи]]

Версия 13:57, 8 апреля 2020