Быстрорастущая иерархия

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Быстрорастущая иерархия (также называемая расширенной иерархией Гржегорчика) — это семейство быстрорастущих функций, индексированных ординалами. Наиболее известным частным случаем быстрорастущей иерархии является иерархия Лёба-Вайнера.

Определение[править | править код]

Быстрорастущая иерархия определяется следующими правилами:

  1. (в общем случае может быть любой растущей функцией),
  2. ,
  3. если предельный ординал,
    • где является n-м элементом фундаментальной последовательности, установленной для некого предельного ординала .
    • Существуют различные версии быстрорастущей иерархии, однако наиболее известной является иерархия Лёба-Вайнера, в которой фундаментальные последовательности для предельных ординалов, записанных в нормальной форме Кантора, определяются следующими правилами:
  4. ,
    • для ,
  5. ,
  6. если предельный ординал,
  7. и .

Фундаментальные последовательности для предельных ординалов свыше приведены в статьях о функциях Веблена и функциях Бухгольца.

Примеры[править | править код]

,

.

Для функций, индексированных конечными ординалами верно

.

В частности, при n=10:

,

,

.

Таким образом, уже первый трансфинитный ординал соответствует пределу стрелочной нотации Кнута.

Знаменитое число Грэма меньше, чем .

Благодаря простоте и ясности определения быстрорастущая иерархия применяется для анализа различных нотаций для записи больших чисел.

нотация Кнута нотация Конвея нотация Бауэрса
предел нотации
примеры

Данная выше дефиниция определяет быстрорастущую иерархию до . Для дальнейшего роста можно использовать функцию Веблена и другие, еще более мощные нотации для ординалов[1].

См. также[править | править код]

Примечания[править | править код]

  1. Kerr, Josh Mind blown: the fast growing hierarchy for laymen — aka enormous numbers. Дата обращения: 7 октября 2016. Архивировано 13 июля 2019 года.

Ссылки[править | править код]

  • Buchholz, W.; Wainer, S.S (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
  • Cichon, E. A.; Wainer, S. S. (1983), "The slow-growing and the Grzegorczyk hierarchies", The Journal of Symbolic Logic, 48 (2): 399—408, doi:10.2307/2273557, ISSN 0022-4812, MR 0704094
  • Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory", Ann. Pure Appl. Logic, 53 (3): 199—260, doi:10.1016/0168-0072(91)90022-E, MR 1129778 (недоступная ссылка) PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
  • Girard, Jean-Yves (1981), "Π12-logic. I. Dilators", Annals of Mathematical Logic, 21 (2): 75—219, doi:10.1016/0003-4843(81)90016-4, ISSN 0003-4843, MR 0656793
  • Löb, M.H.; Wainer, S.S. (1970), "Hierarchies of number theoretic functions", Arch. Math. Logik, 13. Correction, Arch. Math. Logik, 14, 1971. Part I doi:10.1007/BF01967649, Part 2 doi:10.1007/BF01973616, Corrections doi:10.1007/BF01991855.
  • Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", Discrete Mathematics, v.95 n.1-3, p. 341-358, Dec. 1991 doi:10.1016/0012-365X(91)90346-4.
  • Wainer, S.S (1989), "Slow Growing Versus Fast Growing". Journal of Symbolic Logic 54(2): 608-614.