Медленно растущая иерархия

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

Определение

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

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

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

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

Пример

$g_{1}(n)=1$
$g_{m}(n)=m$
$g_{\omega }(n)=n$
$g_{\omega +m}(n)=n+m$
$g_{\omega m}(n)=mn$
$g_{\omega ^{m}}(n)=n^{m}$
$g_{\omega ^{\omega }}(n)=n^{n}$
$g_{\varepsilon _{0}}(n)=n\uparrow \uparrow n$

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

Медленнорастущая иерархия растет гораздо медленнее, чем быстрорастущая иерархия. Даже g _{ε ₀} эквивалентен только f ₃ , а g _α достигает роста f _{ε ₀} (первая функция, которую арифметика Пеано не может доказать полной в иерархии), когда α является ординалом Бахмана–Говарда . ^[2]^[3]^[4]

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

г _α ( п ) < ж _α ( п ) < г _α ( п + 1)

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

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

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

Ссылки

Галье, Жан Х. (1991). «Что такого особенного в теореме Краскала и ординале Γ ₀ ? Обзор некоторых результатов теории доказательств» . Энн. Чистое приложение. Логика . 53 (3): 199–260. дои : 10.1016/0168-0072(91)90022-E . МР 1129778 . См. особенно «Взгляд на иерархии быстро и медленно растущих функций», стр. 59–64 связанной версии.

Примечания

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

[1] Дж. Галье, Что такого особенного в теореме Краскала и ординале Γ ₀ ? Обзор некоторых результатов теории доказательств (2012, стр.63). По состоянию на 8 мая 2023 г.

[girard81-2] Jump up to: ^а ^б Жирар, Жан-Ив (1981). "П ¹_2- логика. I. Расширители» . Анналы математической логики . 21 (2): 75–219. doi : 10.1016/0003-4843(81)90016-4 . ISSN 0003-4843 . MR 0656793 .

[cichon-3] Jump up to: ^а ^б Сишон (1992). «Доказательства завершения и характеристики сложности». У П. Акселя; Х. Симмонс; С. Вайнер (ред.). Теория доказательств . Издательство Кембриджского университета. стр. 173–193.

[wainer83-4] Сичон, Э.А.; Вайнер, СС (1983). «Медленнорастущие иерархии Гжегорчика». Журнал символической логики . 48 (2): 399–408. дои : 10.2307/2273557 . ISSN 0022-4812 . JSTOR 2273557 . МР 0704094 . S2CID 1390729 .

[wainer89-5] Jump up to: ^а ^б Вайнер, СС (1989). «Медленный рост против быстрого роста». Журнал символической логики . 54 (2): 608–614. дои : 10.2307/2274873 . JSTOR 2274873 . S2CID 19848720 .

[weier1997-6] Jump up to: ^а ^б Вейерманн, А (1997). «Иногда медленный рост оказывается быстрым» . Анналы чистой и прикладной логики . 90 (1–3): 91–99. дои : 10.1016/S0168-0072(97)00033-X .

[weier1995-7] Вейерманн, А. (1995). «Исследования медленного и быстрого роста: как нетривиально мажорировать медленно растущие функции с помощью быстрорастущих». Архив математической логики . 34 (5): 313–330. дои : 10.1007/BF01387511 . S2CID 34180265 .

[weier1999-8] Вейерманн, А. (1999), «Что делает (точечную) субрекурсивную иерархию медленно растущей?» Купер, С. Барри (ред.) и др., Множества и доказательства. Приглашенные доклады с коллоквиума Logic '97, Европейской встречи Ассоциации символической логики, Лидс, Великобритания, 6–13 июля 1997 г. Кембридж: Издательство Кембриджского университета. Лонд. Математика. Соц. Лект. Примечание Сер. 258; 403-423.

[weier2001-9] Вейерманн, Андреас (2001). «Γ ₀ может быть минимальным субрекурсивно недоступным». Математическая логика Ежеквартальный журнал . 47 (3): 397–408. doi : 10.1002/1521-3870(200108)47:3<397::AID-MALQ397>3.0.CO;2-Y .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]