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

(перенаправлено с «Быстро растущая иерархия»)

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

Определение

править

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

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

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

Примеры

править

 ,

 .

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

 .

В частности, при 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.