Формально об алгоритмах. Вычислительные модели/Задачи/ex-turing-max-time-grows — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Abondar (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
</latex> | </latex> | ||
| − | [[Category: | + | Для любой 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:На проверку]] | ||
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> | ||
Версия 12:08, 24 ноября 2014
Для любой 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 в бесконечность.
Тем самым мы доказали утверждения для машины конкретной конфигурации машины тьюринга. Значит и для любой машины с бОльшим временем исполнения этот факт останется справедлив => утверждение верно и для маишны с максимальным временем работы.
Утверждение доказано.