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

В теории вычислимости , теории сложности вычислений и теории доказательств быстрорастущая иерархия ( также называемая расширенной иерархией Гжегорчика или иерархией Швихтенберга-Вайнера ) ^[1] представляет собой порядково-индексированное семейство быстро растущих функций f _α : N → N (где N — множество натуральных чисел {0, 1, ...}, а α варьируется до некоторого большого счетного порядкового числа ). Основным примером является иерархия Вайнера , или иерархия Лёба-Вайнера , которая является расширением для всех α < ε 0 . Такие иерархии предоставляют естественный способ классификации вычислимых функций в соответствии со скоростью роста и вычислительной сложностью .

Определение

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

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

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

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

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

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

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

Иерархия Уэйнера

Иерархия Вайнера — это особая быстрорастущая иерархия функций f _α (α ≤ ε 0 ), полученная путем определения фундаментальных последовательностей следующим образом [Gallier 1991][Prӧmel, et al., 1991]:

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

если λ = ω ^{α ₁} + ... + ω ^{α _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 ] = ω ^{ω ^{⋰ ^ω}} с n омегами.

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

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

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

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

Каждая f _α является полной функцией . Если фундаментальные последовательности вычислимы (например, как в иерархии Вайнера), то каждая f _α является полной вычислимой функцией .
В иерархии Вайнера f _α доминируется f _β, если α < β. (Для любых двух функций f , g : N → N говорят , что f доминирует g, если f ( n ) > g ( n ) для всех достаточно больших n .) То же самое свойство сохраняется в любой быстрорастущей иерархии с фундаментальными последовательностями, удовлетворяющими так называемому свойству Бахмана. (Это свойство сохраняется для большинства естественных вполне упорядоченных функций.) ^{[ необходимо разъяснение ]}
В иерархии Гжегорчика каждая примитивно-рекурсивная функция доминируется некоторой f _α с α < ω. Следовательно, в иерархии Вайнера каждая примитивно-рекурсивная функция доминируется f _ω , которая является вариантом функции Аккермана .
При n ≥ 3 множество в иерархии Гжегорчика состоит только из тех общих многоаргументных функций, которые для достаточно больших аргументов вычислимы за время, ограниченное некоторой фиксированной итерацией f _n_-1^{k ,} вычисляемой при максимальном аргументе. ${\mathcal {E}}^{n}$
В иерархии Вайнера каждое f _α с α < ε 0 вычислимо и доказуемо тотально в арифметике Пеано .
Каждая вычислимая функция, которая доказуемо тотальна в арифметике Пеано, доминируется некоторой f _α с α < ε 0 в иерархии Вайнера. Следовательно, f _{ε ₀} в иерархии Вайнера не является доказуемо тотальной в арифметике Пеано.
Функция Гудстейна имеет приблизительно такую же скорость роста ( т.е. каждая из них доминируется некоторой фиксированной итерацией другой) ^{[ требуется ссылка ],} как f _{ε ₀} в иерархии Вайнера, доминируя над каждой f _{α ,} для которой α < ε 0 , и, следовательно, не является доказуемо тотальной в арифметике Пеано.
В иерархии Вайнера, если α < β < ε 0 , то f _β доминирует над каждой вычислимой функцией во времени и пространстве, ограниченном некоторой фиксированной итерацией f _α^k .
Функция TREE Фридмана доминирует над f _{Γ 0} в быстрорастущей иерархии, описанной Галлиером (1991).
Иерархия функций Вайнера f _α и иерархия функций Харди h _α связаны соотношением f _α = h _{ω ^α} для всех α < ε ₀ . Иерархия Харди «догоняет» иерархию Вайнера при α = ε ₀ , так что f _{ε ₀} и h _{ε ₀} имеют одинаковую скорость роста, в том смысле, что f _{ε ₀} ( n -1) ≤ h _{ε ₀} ( n ) ≤ f _{ε ₀} ( n +1) для всех n ≥ 1. (Gallier 1991)
Girard (1981) и Cichon & Wainer (1983) показали, что медленно растущая иерархия функций g _α достигает той же скорости роста, что и функция f _{ε ₀} в иерархии Wainer, когда α является ординалом Бахмана–Ховарда . Girard (1981) далее показал, что медленно растущая иерархия g _α достигает той же скорости роста, что и f _α (в конкретной быстро растущей иерархии), когда α является ординалом теории ID _<ω произвольных конечных итераций индуктивного определения. (Wainer 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 _ω⁶⁴ (64) > число Грэма (= 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 _{ε ₀} ( n ) — первая функция в иерархии Вайнера, которая доминирует над функцией Гудстейна .

Ссылки

^ Беклемишев, Л. Д. (2003). «Анализ теории доказательств с помощью итерационного отражения». Архив журнала «Математическая логика» . 42 (6): 515–552. doi :10.1007/s00153-002-0158-7. S2CID 10454755.

Источники

Бухгольц, В.; Вайнер, С.С. (1987). «Доказуемо вычислимые функции и быстрорастущая иерархия». Логика и комбинаторика , под редакцией С. Симпсона, Contemporary Mathematics, том 65, AMS, 179-198.
Cichon, EA; Wainer, SS (1983), «Медленно растущие и иерархии Гжегорчика», The Journal of Symbolic Logic , 48 (2): 399–408, doi :10.2307/2273557, ISSN 0022-4812, JSTOR 2273557, MR 0704094, S2CID 1390729
Галлье, Жан Х. (1991), «Что такого особенного в теореме Крускала и ординале Γ ₀ ? Обзор некоторых результатов в теории доказательств», Ann. Pure Appl. Logic , 53 (3): 199–260, doi : 10.1016/0168-0072(91)90022-E , MR 1129778PDF: [1]. (В частности, Раздел 12, стр. 59–64, «Взгляд на иерархии быстро и медленно растущих функций».)
Жирар, Жан-Ив (1981), «Π ¹₂ -логика. I. Расширители», Annals of Mathematical Logic , 21 (2): 75–219, doi : 10.1016/0003-4843(81)90016-4 , ISSN 0003-4843, MR 0656793
Löb, MH; Wainer, SS (1970), "Иерархии функций теории чисел", Arch. Math. Logik , 13. Исправление, Arch. Math. Logik , 14, 1971. Часть I doi :10.1007/BF01967649, Часть 2 doi :10.1007/BF01973616, Исправления doi :10.1007/BF01991855.
Prömel, HJ; Thumser, W.; Voigt, B. «Быстрорастущие функции, основанные на теоремах Рамсея», Discrete Mathematics , т.95, № 1-3, стр. 341-358, декабрь 1991 г. doi :10.1016/0012-365X(91)90346-4.
Wainer, SS (1989). «Медленный рост против быстрого роста». Journal of Symbolic Logic . 54 (2): 608–614. doi :10.2307/2274873. JSTOR 2274873. S2CID 19848720.