Просмотр исходного текста страницы Формально об алгоритмах. Вычислительные модели/Задачи/ex-turing-max-time-grows

<latex>
Пусть $T(n)$~---~максимальное время, которое может пройти до
остановки машины Тьюринга с~$n$ состояниями и~$n$ символами
алфавита, если ее запустить на пустой ленте. Докажите, что.
функция $T(n)$ растет быстрее любой вычислимой всюду
определенной функции $b(n)$, то есть $\lim [T(n)/b(n)]=+\infty$.
</latex>


<!--Вообще-то, решения уже есть-->

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]