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

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

Определение [ править ]

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

Достопримечательности [ править ]

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

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

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

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

ж ₀ ( п ) знак равно п + 1 знак равно 2 [1] п - 1
ж ₁ ( п ) знак равно ж ₀^н( п ) знак равно п + п знак равно 2 п знак равно 2[2] п
f2 ( п = f1 ₎^н( п ) знак равно 2 ^н · п > 2 ^н = 2[3] n для n ≥ 2
ж _{k +1} ( п ) знак равно ж _k^н( п ) > (2[ к + 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 _ω является унарной версией).
ж _ω+1 ( п ) знак равно ж _ω^н( 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ε0 _{над _{функцией}} ( n ) — первая функция в иерархии Вайнера, которая доминирует Гудштейна .

Ссылки [ править ]

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

Источники [ править ]

Бухгольц, В.; Вайнер, СС (1987). «Доказуемо вычислимые функции и быстрорастущая иерархия». Логика и комбинаторика , под редакцией С. Симпсона, Contemporary Mathematics, Vol. 65, АМС, 179–198.
Сичон, Э.А.; Вайнер, С.С. (1983), «Медленнорастущие иерархии Гжегорчика», Журнал символической логики , 48 (2): 399–408, doi : 10.2307/2273557 , ISSN 0022-4812 , JSTOR 2273557 , MR 0704094 , S2CID 1390729
Галье, Жан Х. (1991), «Что такого особенного в теореме Краскала и ординале Γ ₀ ? Обзор некоторых результатов теории доказательств», Ann. Чистое приложение. Logic , 53 (3): 199–260, doi : 10.1016/0168-0072(91)90022-E , MR 1129778 PDF: [1] . (В частности, раздел 12, стр. 59–64, «Взгляд на иерархии быстро и медленно растущих функций».)
Жирар, Жан-Ив (1981), «Π ¹_2- логика. I. Расширители», Annals of Mathematical Logic , 21 (2): 75–219, doi : 10.1016/0003-4843(81)90016-4 , ISSN 0003-4843 , MR 0656793
Лёб, МХ; Вайнер, СС (1970), "Иерархии теоретико-числовых функций", Arch. Математика. Логик , 13. Исправление, Арх. Математика. Логик , 14, 1971. Часть I doi : 10.1007/BF01967649 , Часть 2 doi : 10.1007/BF01973616 , Исправления два : 10.1007/BF01991855 .
Премель, Х.Ю.; Тамсер, В.; Фойгт, Б. «Быстрорастущие функции на основе теорем Рамсея», Дискретная математика , т.95, н.1-3, с. 341-358, декабрь 1991 г. два : 10.1016/0012-365X(91)90346-4 .
Вайнер, СС (1989). «Медленный рост против быстрого роста». Журнал символической логики . 54 (2): 608–614. дои : 10.2307/2274873 . JSTOR 2274873 . S2CID 19848720 .

[1] Беклемишев, Л.Д. (2003). «Теоретико-доказательный анализ методом повторного размышления» . Архив математической логики . 42 (6): 515–552. дои : 10.1007/s00153-002-0158-7 . S2CID 10454755 .

[1]