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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

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

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

ж₀(п) = п + 1 = 2 [1] п − 1
ж₁(п) = ж₀^п(п) = п + п = 2п = 2 [2] п
ж₂(п) = ж₁^п(п) = 2^п · п > 2^п = 2 [3] п для п ≥ 2
ж_k+1(п) = ж_k^п(п) > (2 [k + 1])^п п ≥ 2 [k + 2] п для п ≥ 2, k <ω.

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

ж_ω(п) = ж_п(п) > 2 [п + 1] п > 2 [п] (п + 3) − 3 = А(п, п) для п ≥ 4, где А это Функция Аккермана (из которых ж_ω это унарная версия).
ж_{ω + 1}(п) = ж_ω^п(п) ≥ f_{п [п + 2] п}(п) для всех п > 0, где п [п + 2] п это п^th Число Аккермана.
ж_{ω + 1}(64) > ж_ω⁶⁴(6) > Число Грэма (= г₆₄ в последовательности, определяемой г₀ = 4, г_k+1 = 3 [г_k + 2] 3). Это следует, отмечая ж_ω(п) > 2 [п + 1] п > 3 [п] 3 + 2 и, следовательно, ж_ω(г_k + 2) > г_k+1 + 2.
ж_ε₀(п) - первая функция в иерархии Вейнера, которая доминирует над Функция Гудштейна.

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

Buchholz, W .; Вайнер, С.С. (1987). «Доказанно вычислимые функции и быстрорастущая иерархия». Логика и комбинаторика, под редакцией С. Симпсона, Contemporary Mathematics, Vol. 65, AMS, 179–198.
Cichon, E.A .; Вайнер, С. С. (1983), "Медленнорастущие и иерархии Гжегорчика", Журнал символической логики, 48 (2): 399–408, Дои:10.2307/2273557, ISSN 0022-4812, Г-Н 0704094
Галье, Жан Х. (1991), "Что такого особенного в теореме Крускала и ординале Γ?₀? Обзор некоторых результатов теории доказательств », Анна. Pure Appl. Логика, 53 (3): 199–260, Дои:10.1016 / 0168-0072 (91) 90022-Е, Г-Н 1129778^{[постоянная мертвая ссылка ]} PDF: [1]. (В частности, раздел 12, стр. 59–64, «Взгляд на иерархии быстро и медленно растущих функций».)
Жирар, Жан-Ив (1981),¹₂-логика. I. Дилататоры », Анналы математической логики, 21 (2): 75–219, Дои:10.1016/0003-4843(81)90016-4, ISSN 0003-4843, Г-Н 0656793
Löb, M.H .; Вайнер, С.С. (1970), "Иерархии теоретико-числовых функций", Arch. Математика. Логик, 13. Поправка, Arch. Математика. Логик, 14, 1971. Часть I Дои:10.1007 / BF01967649, Часть 2 Дои:10.1007 / BF01973616, Исправления Дои:10.1007 / BF01991855.
Prömel, H.J .; Thumser, W .; Фойгт, Б. "Быстрорастущие функции, основанные на теоремах Рамсея", Дискретная математика, т.95, п.1-3, с. 341-358, декабрь 1991 г. Дои:10.1016 / 0012-365X (91) 90346-4.
Вайнер, С.С. (1989). «Медленный рост против быстрого роста». Журнал символической логики. 54 (2): 608–614. JSTOR 2274873.