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

редактировать

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

Содержание

1 Определение
2 Иерархия Вейнера
3 балла представляющих интерес
4 Функции в быстрорастущих иерархиях
5 Ссылки

Определение

Пусть μ будет большим счетным порядковым номером, таким как каждый предельный порядковый номер α < μ there is assigned a фундаментальная последовательность (строго возрастающая последовательность порядковых чисел, верхняя грань которой равна α). A быстрорастущая иерархия функций f α: N→ N, для α < μ, is then defined as follows:

$f 0 (n) = n + 1, {\ displaystyle f_ {0} (n) = n + 1,}$ ${\ displaystyle f_ {0} (n) = n + 1,}$
$е α + 1 (N) = е α N (N), {\ Displaystyle f _ {\ alpha +1} (n) = f _ {\ alpha} ^ {n} (n),}$ ${\ displaystyle f _ {\ alpha +1} ( n) = f _ {\ alpha} ^ {n} (n),}$
$f α (n) = f α [n] (n) {\ displaystyle f _ {\ alpha} (n) = f _ {\ alpha [n]} (n)}$ ${\ displaystyle f _ {\ alpha} (n) = f _ {\ alpha [n]} (n)}$ , если α - предельный порядковый номер.

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

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

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

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

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

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

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

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

, если λ = ω +... + ω + ω для α 1 ≥... ≥ α k − 1 ≥ α k, тогда λ [n] = ω +... + ω + ω [n],
если λ = ω, то λ [n] = ωn,
если λ = ω для предельного ординала α, то λ [n] = ω,

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

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

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

Интересные моменты

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

Каждое f α является общей функцией. Если фундаментальные последовательности вычислимы (например, как в иерархии Вейнера), то каждое f α является общей вычислимой функцией.
В иерархии Вейнера, f α доминирует f β, если α < β. (For any two functions f, g: N→ N, говорят, что f доминирует над g, если f (n)>g (n) для всех достаточно больших n.) То же свойство выполняется в любой быстрорастущей иерархии с фундаментальными последовательностями, удовлетворяющими т. н. (Это свойство сохраняется для большинства естественных порядков колодцев.)
В иерархии Гжегорчика каждая примитивно рекурсивная функция подчиняется некоторому f α с α < ω. Hence, in the Wainer hierarchy, every primitive recursive function is dominated by fω, который является вариантом функции Аккермана.
Для n ≥ 3 набор $E n {\ displaystyle {\ mathcal {E}} ^ {n}}$ ${\ mathcal {E}} ^ {n}$ в иерархии Гжегорчика состоит только из тех полных функций с несколькими аргументами, которые при достаточно больших аргументах вычисляются в течение времени, ограниченного некоторой фиксированной итерацией f n-1, вычисляемой в максимальный аргумент.
В иерархии Вейнера каждое f α с α < ε0 вычислимо и доказуемо суммируется в арифметике Пеано.
Каждая вычислимая функция, которая доказуемо является суммой в Пеано В арифметике преобладают некоторые f α с α < ε0 в иерархии Вейнера. Следовательно, f ε0в иерархии Вейнера не является доказуемо полным в арифметике Пеано.
Функция Гудштейна имеет примерно одинаковую скорость роста (т. Е. В каждой из них преобладает некоторая фиксированная итерация другой) как f ε0в иерархии Вейнера, доминируя над каждым f α, для которого α < ε0, и, следовательно, не является доказуемо полным в арифметике Пеано.
В иерархии Вейнера, если α < β < ε0, тогда f β доминирует над каждой вычислимой функцией во времени и пространстве, ограниченном некоторой фиксированной итерацией f α.
ДЕРЕВО Фридмана функция доминирует над f Γ0 в быстрорастущей иерархии, описываемой Gallier (1991).
Иерархия Вейнера функций f α и иерархия Харди функций h α связаны соотношением f α = h ω для всех α < ε0. Иерархия Харди «догоняет» иерархию Вейнера при α = ε 0, так что f ε0и h ε0имеют одинаковую скорость роста в том смысле, что f ε0(n -1) ≤ h ε0(n) ≤ f ε0(n + 1) для всех n ≥ 1. (Gallier 1991)
Girard (1981) и Cichon Wainer (1983) показали, что медленно растущая иерархия функций g α достигает той же скорости роста, что и функция f ε0в иерархии Вейнера, когда α является ординалом Бахмана – Ховарда. Жирар (1981) далее показал, что медленнорастущая иерархия g α достигает той же скорости роста, что и f α (в конкретной быстрорастущей иерархии), когда α является порядковым номером теория ID <ωпроизвольных конечных итераций индуктивного определения. (Wainer 1989)

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

Функции на конечных уровнях (α < ω) of any fast-growing hierarchy coincide with those of the Grzegorczyk hierarchy: (using гипероперация )

f0(n) = n + 1 = 2 [1] n - 1
f1(n) = f 0 (n) = n + n = 2n = 2 [2] n
f2(n) = f 1 (n) = 2 · n>2 = 2 [3] n для n ≥ 2
fk + 1 (n) = f k (n)>(2 [k + 1]) n ≥ 2 [k + 2] n для n ≥ 2, k < ω.

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

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 ω (6)>Число Грэма (= g 64 в последовательности, определяемой g 0 = 4, g k + 1 = 3 [g k + 2] 3). Это следует из того, что f ω (n)>2 [n + 1] n>3 [n] 3 + 2, и, следовательно, f ω(gk+ 2)>g k + 1 + 2.
fε0(n) - первая функция в иерархии Вейнера, которая доминирует в функции Гудштейна.

Ссылки

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