WikiDer > Иерархия Харди - Википедия

В теория вычислимости, теория сложности вычислений и теория доказательств, то Харди иерархия, названный в честь Г. Х. Харди, является индексированным по порядку семейством функций час_α: N → N (куда N это набор натуральные числа, {0, 1, ...}). Это связано с быстрорастущая иерархия и медленно растущая иерархия. Иерархия была впервые описана в статье Харди 1904 г. «Теорема о бесконечных кардинальных числах».

Определение

Пусть μ - большой счетный порядковый номер так что основная последовательность назначается каждому предельный порядковый номер меньше μ. В Харди иерархия функций час_α: N → N, за α < μ, тогда определяется следующим образом:

• ${ displaystyle h_ {0} (п) = п,}$
• ${ Displaystyle ч _ { альфа +1} (п) = ч _ { альфа} (п + 1),}$
• ${ Displaystyle ч _ { альфа} (п) = ч _ { альфа [п]} (п)}$ если α - предельный ординал.

Здесь α [п] обозначает п^th элемент фундаментальной последовательности, присвоенный предельному порядковому номеруα. Стандартизированный выбор фундаментальной последовательности для всехα ≤ ε₀ описано в статье о быстрорастущая иерархия.

Caicedo (2007) определяет модифицированную иерархию функций Харди. ${ displaystyle H _ { alpha}}$ используя стандартные фундаментальные последовательности, но с α [п+1] (вместо α [п]) в третьей строке приведенного выше определения.

Отношение к быстрорастущей иерархии

В Иерархия Wainer функций ж_α и иерархия функций Харди час_α связаны ж_α = час_ω^α для всех α <ε₀. Таким образом, для любого α <ε₀, час_α растет намного медленнее, чем ж_α. Однако иерархия Харди «догоняет» иерархию Вейнера при α = ε₀, так что ж_ε0 и час_ε0 имеют одинаковые темпы роста в том смысле, что ж_ε0(п-1) ≤ час_ε0(п) ≤ ж_ε0(п+1) для всех п ≥ 1. (Галье 1991)

Рекомендации

• Харди, Г. (1904), «Теорема о бесконечных кардинальных числах», Ежеквартальный журнал математики, 35: 87–94
• Галье, Жан Х. (1991), "Что такого особенного в теореме Крускала и ординале Γ?₀? Обзор некоторых результатов теории доказательств » (PDF), Анна. Pure Appl. Логика, 53 (3): 199–260, Дои:10.1016 / 0168-0072 (91) 90022-Е, МИСТЕР 1129778. (В частности, раздел 12, стр. 59–64, «Взгляд на иерархии быстро и медленно растущих функций».)
• Кайседо, А. (2007), «Функция Гудштейна» (PDF), Revista Colombiana de Matemáticas, 41 (2): 381–391.