Медленно растущая иерархия - Slow-growing hierarchy

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

Определение

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

• ${\displaystyle g_{0}(n)=0}$
• ${\displaystyle g_{k+1}(n)=g_{k}(n)+1}$
• ${\displaystyle g_{\alpha }(n)=g_{\alpha [n]}(n)}$ для предельного ординала α.

Здесь α [п] обозначает п^th элемент фундаментальной последовательности, назначенный предельному ординалу α.

Статья о Быстрорастущая иерархия описывает стандартизованный выбор фундаментальной последовательности для всех α <ε₀.

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

Медленнорастущая иерархия растет намного медленнее, чем быстрорастущая иерархия. Четное грамм_ε0 только эквивалентно ж₃ и грамм_α только достигает роста ж_ε0 (первая функция, которая Арифметика Пеано не могу доказать общий в иерархии), когда α - Порядковый номер Бахмана – Ховарда.^[1][2][3]

Однако Жирар доказал, что медленно растущая иерархия в конечном итоге догоняет с быстрорастущей.^[1] В частности, существует ординал α такой, что для всех целых чисел п

грамм_α(п) < ж_α(п) < грамм_α(п + 1)

куда ж_α - это функции в быстрорастущей иерархии. Далее он показал, что первое α, для которого это верно, является ординалом теории Я БЫ_<ω произвольных конечных итераций индуктивного определения.^[4] Однако для задания фундаментальных последовательностей, найденных в ^[2] первое совпадение происходит на уровне ε₀.^[5] Для порядковых номеров дерева в стиле Бухгольца можно показать, что первое совпадение даже происходит в ${\displaystyle \omega ^{2}}$.

Обобщения доказанного результата^[4] к значительно большим ординалам показывает, что очень мало ординалов ниже ординала трансконечно повторяемого ${\displaystyle \Pi _{1}^{1}}$-понимание того, где совпадают медленно и быстро растущая иерархия.^[6]

Медленно растущая иерархия чрезвычайно чувствительно зависит от выбора лежащих в основе фундаментальных последовательностей.^[5][7][8]

Отношение к переписыванию терминов

Cichon представил интересную связь между медленно растущей иерархией и длиной вывода для переписывания терминов.^[2]

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

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

Примечания

1. Жирар, Жан-Ив (1981). "Π¹₂-логика. I. Дилататоры ». Анналы математической логики. 21 (2): 75–219. Дои:10.1016/0003-4843(81)90016-4. ISSN  0003-4843. МИСТЕР  0656793.
2. Cichon (1992). «Доказательства прекращения и характеристики сложности». У П. Акзеля; Х. Симмонс; С. Вайнер (ред.). Теория доказательства. Издательство Кембриджского университета. С. 173–193.
3. Cichon, E.A .; Вайнер, С. С. (1983). «Медленнорастущие иерархии и иерархии Гжегорчика». Журнал символической логики. 48 (2): 399–408. Дои:10.2307/2273557. ISSN  0022-4812. JSTOR  2273557. МИСТЕР  0704094.
4. Вайнер, С. С. (1989). «Медленный рост против быстрого роста». Журнал символической логики. 54 (2): 608–614. Дои:10.2307/2274873. JSTOR  2274873.
5. Вейерманн, А (1997). «Иногда медленный рост быстро растет». Анналы чистой и прикладной логики. 90 (1–3): 91–99. Дои:10.1016 / S0168-0072 (97) 00033-X.
6. Вейерманн, А. (1995). «Исследования медленного и быстрого роста: как нетривиально мажорировать медленнорастущие функции с помощью быстрорастущих». Архив по математической логике. 34 (5): 313–330. Дои:10.1007 / BF01387511.
7. Вейерманн, А. (1999), «Что замедляет рост (точечной) субрекурсивной иерархии?» Купер, С. Барри (ред.) И др., Наборы и доказательства. Приглашенные доклады с коллоквиума по логике '97, Европейской встречи Ассоциации символической логики, Лидс, Великобритания, 6–13 июля 1997 г. Кембридж: Cambridge University Press. Лондон. Математика. Soc. Lect. Примечание Сер. 258; 403-423.
8. Вейерманн, Андреас (2001). "Γ₀ Может быть минимально субрекурсивно недоступным ». Mathematical Logic Quarterly. 47 (3): 397–408. Дои:10.1002 / 1521-3870 (200108) 47: 3 <397 :: AID-MALQ397> 3.0.CO; 2-Y.