Быстрорастущая иерархия - Fast-growing hierarchy

В теории вычислимости , теории сложности вычислений и теории доказательств , А быстрорастущая иерархия (также называется расширенная иерархия Гжегорчика ) является порядковым-индексированным семейством быстро растущими функций F _{& alpha} ; : N → N (где N есть множество натуральных чисел { 0, 1, ...}, а α принимает значения до некоторого большого счетного порядкового номера ). Первичный пример - иерархия Вейнера или иерархия Лёба – Вейнера , которая является расширением для всех α < ε ₀ . Такие иерархии обеспечивают естественный способ классификации вычислимых функций в соответствии со скоростью роста и вычислительной сложностью .

Определение

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

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

Здесь е _{& alpha ;} ^п ( п ) = е _{& alpha} ; ( е _{& alpha} ; (... ( F _{& alpha} ; ( п )) ...)) обозначает п - ^й итерации F _α применительно к п и α [ п ] обозначает п - ^й элемент фундаментальной последовательности, назначенный предельному ординалу α. (В альтернативном определении количество итераций во второй строке выше должно быть n +1, а не n .)

Начальная часть этой иерархии, состоящая из функций f _α с конечным индексом (т. Е. Α <ω), часто называется иерархией Гжегорчика из-за ее тесной связи с иерархией Гжегорчика ; обратите внимание, однако, что первое здесь является индексированным семейством функций f _n , тогда как второе является индексированным семейством наборов функций . (См. Интересные места ниже.) ${\ displaystyle {\ mathcal {E}} ^ {n}}$

Обобщая приведенное выше определение , даже Кроме того, быстрая иерархия итерации получается, если взять F ₀ , чтобы быть любой возрастающей функцией г: N → N .

Для предельных ординалов, не превышающих ε ₀ , существует простое естественное определение фундаментальных последовательностей (см. Иерархию Вейнера ниже), но за пределами ε ₀ определение намного сложнее. Однако это возможно далеко за пределами ординала Фефермана – Шютте, Γ ₀ , по крайней мере до ординала Бахмана – Ховарда . Используя пси-функции Бухгольца, можно легко расширить это определение до ординала трансконечно итерированного -понимания (см. Аналитическая иерархия ). ${\ displaystyle \ Pi _ {1} ^ {1}}$

Полностью указанное расширение за пределами рекурсивных порядковых номеров считается маловероятным; например, Prӧmel et al. [1991] (стр. 348) отмечают, что при такой попытке «даже возникнут проблемы с порядковой записью».

Иерархия Вейнера

Иерархия Wainer является особенно быстрорастущей иерархией функций F _{& alpha} ; ( & le ; & alpha ; & epsi ; ₀ ) , полученного путем определения основных последовательностей следующим образом [Gallier 1991] [Prӧmel, и др . , 1991]:

Для предельных ординалов λ < ε ₀ , записанных в нормальной форме Кантора ,

• если λ = ω ^{α ₁} + ... + ω ^{α _{k − 1}} + ω ^{α _k} для α ₁ ≥ ... ≥ α _{k − 1} ≥ α _k , то λ [ n ] = ω ^{α ₁} + ... + ω ^{α _{k − 1}} + ω ^{α _k} [ n ],
• если λ = ω ^{α + 1} , то λ [ n ] = ω ^α n ,
• если λ = ω ^α для предельного ординала α, то λ [ n ] = ω ^{α [ n ]} ,

а также

• если λ = ε ₀ , возьмем λ [0] = 0 и λ [ n + 1] = ω ^{λ [ n ],} как в [Gallier 1991]; в качестве альтернативы, возьмите ту же последовательность, но начиная с λ [0] = 1, как в [Prӧmel, et al., 1991].
  При n > 0 альтернативная версия имеет одно дополнительное ω в результирующей экспоненциальной башне, то есть λ [ n ] = ω ^{ω . . . ω} с п Омеги.

Некоторые авторы используют несколько иные определения (например, ω ^{α + 1} [ n ] = ω ^α ( n + 1 ) вместо ω ^α n ), а некоторые определяют эту иерархию только для α <ε ₀ (таким образом, исключая f _{ε 0} из иерархия).

Чтобы продолжить за пределами ε ₀ , см. Основные последовательности иерархии Веблена .

Точки интереса

Ниже приведены некоторые важные моменты, связанные с быстрорастущими иерархиями:

• Каждая f _α является полной функцией . Если фундаментальные последовательности вычислимы (например, как в иерархии Вейнера), то каждая f _α является полной вычислимой функцией .
• В иерархии Вейнера, f _α преобладает над f _β, если α <β. (Для любых двух функций f , g : N → N говорят , что f доминирует над g, если f ( n )> g ( n ) для всех достаточно больших n .) То же свойство имеет место в любой быстрорастущей иерархии с фундаментальными последовательностями, удовлетворяющими так называемое свойство Бахмана . (Это свойство верно для большинства естественных порядков колодцев.)
• В иерархии Гжегорчика каждая примитивно рекурсивная функция подчиняется некоторому f _α с α <ω. Следовательно, в иерархии Вейнера для каждой примитивной рекурсивной функции доминирует f _ω , которая является вариантом функции Аккермана .
• При n ≥ 3 набор в иерархии Гжегорчика состоит только из тех полных функций с несколькими аргументами, которые при достаточно больших аргументах вычислимы в течение времени, ограниченного некоторой фиксированной итерацией f _{n -1} ^k, вычисляемой при максимальном аргументе.${\ displaystyle {\ mathcal {E}} ^ {n}}$
• В иерархии Вейнера каждое f _α с α < ε ₀ вычислимо и доказуемо тотально в арифметике Пеано .
• Каждая вычислимая функция, доказуемо полная в арифметике Пеано, подчиняется некоторому f _α с α < ε ₀ в иерархии Вейнера. Следовательно, f _{ε 0} в иерархии Вейнера не доказуемо тотально в арифметике Пеано.
• Функция Гудстейна имеет примерно такую ​​же скорость роста ( т. Е. В каждой из них доминирует какая-то фиксированная итерация другой), что и у f _{ε 0} в иерархии Вейнера, доминируя для всех f _α, для которых α < ε ₀ , и, следовательно, не является доказуемо полной в Пеано. Арифметика.
• В иерархии Вейнера, если α <β < ε ₀ , то f _β доминирует над любой вычислимой функцией в пределах времени и пространства, ограниченных некоторой фиксированной итерацией f _α ^k .
• Функция ДЕРЕВО Фридмана доминирует над f _{Γ 0} в быстрорастущей иерархии, описанной Галлиером (1991).
• Иерархия Вейнера функций f _α и иерархия Харди функций h _α связаны соотношением f _α = h _{ω ^α} для всех α <ε ₀ . Иерархия Харди «догоняет» иерархию Вейнера при α = ε ₀ , так что f _{ε 0} и h _{ε 0} имеют одинаковую скорость роста в том смысле, что f _{ε 0} ( n -1) ≤ h _{ε 0} ( n ) ≤ f _{ε 0} ( n +1) для всех n ≥ 1. (Галлье, 1991)
• Girard (1981) и Cichon & Wainer (1983) показали, что медленно растущая иерархия функций g _α достигает той же скорости роста, что и функция f _{ε 0} в иерархии Вейнера, когда α является ординалом Бахмана – Ховарда . Жирар (1981) далее показал, что медленно растущая иерархия g _α достигает той же скорости роста, что и f _α (в конкретной быстрорастущей иерархии), когда α - порядковый номер теории ID _<ω произвольных конечных итераций индуктивного определения . (Вайнер 1989)

Функции в быстрорастущих иерархиях

Функции на конечных уровнях (α <ω) любой быстрорастущей иерархии совпадают с функциями иерархии Гжегорчика: (с использованием гипероперации )

• f ₀ ( n ) = n + 1 = 2 [1] n - 1
• f ₁ ( n ) = f ₀ ⁿ ( n ) = n + n = 2 n = 2 [2] n
• f ₂ ( n ) = f ₁ ⁿ ( n ) = 2 ⁿ · n > 2 ⁿ = 2 [3] n для n ≥ 2
• f _{k +1} ( n ) = f _k ⁿ ( n )> (2 [ k + 1]) ⁿ n ≥ 2 [ k + 2] n для n ≥ 2, k <ω.

За конечными уровнями находятся функции иерархии Вейнера (ω ≤ α ≤ ε ₀ ):

• f _ω ( n ) = f _n ( n )> 2 [ n + 1] n > 2 [ n ] ( n + 3) - 3 = A ( n , n ) для n ≥ 4, где A - функция Аккермана ( из которых f _ω - унарная версия).
• f _{ω + 1} ( n ) = f _ω ⁿ ( n ) ≥ f _{n [ n + 2] n} ( n ) для всех n > 0, где n [ n + 2] n - n- ^е число Аккермана .
• f _{ω + 1} (64)> f _ω ⁶⁴ (5)> число Грэма (= g ₆₄ в последовательности, определенной как g ₀ = 4, g _{k +1} = 3 [ g _k + 2] 3). Это следует из того, что f _ω ( n )> 2 [ n + 1] n > 3 [ n ] 3 + 2, и, следовательно, f _ω ( g _k + 2)> g _{k +1} + 2.
• f _{ε 0} ( n ) - первая функция в иерархии Вейнера, которая доминирует над функцией Гудштейна .

использованная литература

• Buchholz, W .; Уайнер, СС (1987). «Доказуемо вычислимые функции и быстрорастущая иерархия». Логика и комбинаторика , под редакцией С. Симпсона, Contemporary Mathematics, Vol. 65, AMS, 179–198.
• Cichon, EA; Вайнер, SS (1983), "медленно растущие и иерархии Grzegorczyk", Журнал символической логики , 48 (2): 399-408, DOI : 10,2307 / 2273557 , ISSN  0022-4812 , MR  0704094
• Gallier, Jean H. (1991), "Что такого особенного в теореме Крускала и ординале Γ ₀ ? Обзор некоторых результатов в теории доказательств", Ann. Pure Appl. Логика , 53 (3): 199-260, DOI : 10.1016 / 0168-0072 (91) 90022-Е , МР  1129778PDF: [1] . (В частности, раздел 12, стр. 59–64, «Взгляд на иерархии быстро и медленно растущих функций».)
• Girard, Жан-Ив (1981), "Π ¹ ₂ -logic I. Расширители.", Анналы математической логики , 21 (2): 75-219, DOI : 10,1016 / 0003-4843 (81) 90016-4 , ISSN  0003-4843 , Руководство по ремонту  0656793
• Лёб, MH; Wainer, SS (1970), "Иерархии теоретико-числовых функций", Arch. Математика. Логик , 13. Исправление, Арх. Математика. Logik , 14, 1971. Часть I doi : 10.1007 / BF01967649 , Часть 2 doi : 10.1007 / BF01973616 , Исправления doi : 10.1007 / BF01991855 .
• Prömel, HJ; Thumser, W .; Фойгт, Б. "Быстрорастущие функции, основанные на теоремах Рамсея", Дискретная математика , т.95, №1-3, с. 341-358, декабрь 1991 г. DOI : 10.1016 / 0012-365X (91) 90346-4 .
• Уайнер, СС (1989). «Медленный рост против быстрого роста». Журнал символической логики . 54 (2): 608–614. JSTOR  2274873 .