Изменения

Перейти к: навигация, поиск

Теорема Ладнера

5 байт добавлено, 16:07, 3 июня 2012
Нет описания правки
Положим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex> построим <tex>g(n + 1)</tex> рекурсивно — с помощью <tex>g(0), g(1), \ldots, g(n)</tex>.
* Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов.
* Пусть вычисленное значение <tex>g(n)</tex> чётно. Определим <tex>g(n+1)</tex> так:

Навигация