Быстрорастущая иерархия (также называемая расширенной иерархией Гржегорчика) — это семейство быстрорастущих функций, индексированных ординалами. Наиболее известным частным случаем быстрорастущей иерархии является иерархия Лёба-Вайнера.
Определение
Быстрорастущая иерархия определяется следующими правилами: (в общем случае может быть любой растущей функцией), , если предельный ординал, где является n-м элементом фундаментальной последовательности, установленной для некого предельного ординала . Существуют различные версии быстрорастущей иерархии, однако наиболее известной является иерархия Лёба-Вайнера, в которой фундаментальные последовательности для предельных ординалов, записанных в нормальной форме Кантора, определяются следующими правилами: ,
для , , если предельный ординал, и . Фундаментальные последовательности для предельных ординалов свыше приведены в статьях о функциях Веблена и функциях Бухгольца.
Примеры
,
.
Для функций, индексированных конечными ординалами верно
.
В частности, при n=10:
,
,
.
Таким образом, уже первый трансфинитный ординал соответствует пределу стрелочной нотации Кнута.
Знаменитое число Грэма меньше, чем .
Благодаря простоте и ясности определения быстрорастущая иерархия применяется для анализа различных нотаций для записи больших чисел. нотация Кнута нотация Конвея нотация Бауэрсапредел нотациипримеры Данная выше дефиниция определяет быстрорастущую иерархию до . Для дальнейшего роста можно использовать функцию Веблена и другие, ещё более мощные нотации для ординалов.
(см. Стрелочная нотация Кнута)
(см. Массивная нотация Бауэрса) (см. Число Грэма)
(m раз) (n раз)
(см. Bird's Array Notation)
(m обратных слэшей)
(см. TREE(3))
(см. Bashicu Matrix System)
См. также Медленнорастущая иерархия Иерархия Харди Примечания
Ссылки
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.
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".)
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 , Part 2 , Corrections . 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 . Wainer, S.S (1989), "Slow Growing Versus Fast Growing". Journal of Symbolic Logic 54(2): 608-614.
Категория:Функции Категория:Большие числа Категория:Теория доказательств