Быстрорастущая иерархия (сокращённо БРИ) — определённая иерархия, отображающая ординалы (ниже верхней границы фиксированной системы фундаментальных последовательностей) к набору функций, которые порождены из быстрорастущих функций, обозначаемых . Для больших ординалов , может расти очень быстро. Благодаря простому и ясному определению, а также своему происхождению из профессиональной математики, БРИ является популярным эталоном для функций, выдающих большие числа.
Читатель должен быть очень внимателен к тому, что на личном веб-сайте, в видео и блогах пользователей много неправильных "введений", хотя, к сожалению, новички предпочитают именно их. Поскольку математические понятия, такие как ординалы и фундаментальные последовательности, довольно абстрактны и с ними трудно обращаться точным образом, люди склонны давать их интуитивные описания, которые для начинающих они выглядят проще и круче, чем точные объяснения. Однако такие "введения" часто содержат серьёзные ошибки, поскольку авторы также изучали их по другим интуитивным описаниям вместо точных определений. Важным моментом является то, что точное описание их на самом деле необходимо для понимания быстрорастущей иерархии. Причина, по которой точные описания выглядят сложными, заключается не в том, что они просто плохо написаны или избыточны, а в том, что понятия на самом деле довольно сложны, хотя такие неправильные "введения" иногда объясняют их как простые понятия.
Если вы не знакомы с использованием ординалов в функциях, вы можете прочитать статью Введение в быстрорастущую иерархию. Кроме того, будьте осторожны: существует много неправильных описаний вычислимости функций в быстрорастущей иерархии. Хотя гугологи иногда утверждают, что данная функция вычислима, потому что она задаётся быстрорастущей иерархией, это типичная ошибка. Функция, определённая методом, использующим бесконечные ординалы, например, в быстрорастущей иерархии, не обязательно является вычислимой. Чтобы гарантировать вычислимость функции, определенной в быстрорастущей иерархии, нам необходимо построить явный алгоритм для его вычисления, и типичным примером является алгоритм для фундаментальных последовательностей в ординальной нотации. Такие маленькие функции, как в быстрорастущей иерархии, могут быть невычислимы без определения с использованием явного алгоритма. Поскольку алгоритм принимает только элементы счётного набора с фиксированным перечислением, бесконечные ординалы в наборе без фиксированного перечисления не допускаются. Для решения вопроса о вычислимости мы часто используем ординальные нотации.
Один из наиболее важных фактов о быстрорастущей иерархии (вместе с похожими на неё функциями, например, иерархия Харди и медленнорастущая иерархия) заключается в том, что она плохо определена, если только не конкретный выбор системы фундаментальных последовательностей явно фиксируется в контексте. Новичкам следует быть очень осторожными в этом вопросе, потому что такого рода нечёткость часто возникает, когда гугологи говорят о ловле ординалов, ординале, рассматриваемом как скорость роста, теоретико-доказательный ординал в быстрорастущей иерархии и так далее без понимания зависимости выбора системы фундаментальных последовательностей.
Быстрорастущая функция состоит из ординальной системы и системы фундаментальной последовательности, где обозначает , а обозначает класс предельных ординалов. Семантика следующая:
Здесь обозначает -й член фиксированной фундаментальной последовательности, присвоенной ординалу . Система фундаментальных последовательностей для предельных ординалов ниже заданного супремума не уникальна, и быстрорастущая иерархия во многом зависит от выбора такой системы, как мы объясняли в разделе "Предупреждение".
Некоторые авторы вместо этого устанавливают для второй строки.[1]
Чтобы быстрорастущая иерархия была полезна гугологам, она также должна удовлетворять свойству, которое для всех , в конечном итоге доминирует над , хотя это не обязательно верно для общей системы фундаментальных последовательностей.[2][3] Читатель должен быть осторожен, так как многие гугологи не знают этого факта и неявно предполагают это свойство даже тогда, когда в контексте нет доказательств конкретной системы фундаментальной последовательности. Смотрите также Ординал Чёрча-Клини#Быстрорастущая иерархия для ознакомления с распространёнными заблуждениями, связанными с быстрорастущей иерархией.
Быстрорастущая иерархия[]
Быстрорастущая иерархия определяется как Иерархия Гжегорчика. Для каждого ординала набор числовых функций определяется как наименьший класс, удовлетворяющий следующим условиям:
Это содержит
нулевую константу, обозначаемую как ,
функцию-преемника,
проекционную функцию и
быстрорастущую функцию.
Он закрыт под
заменой, для и
ограниченной рекурсией, , для и leq M(n,x_1,\dots,x_n)</math> для некоторого
Общий случай, когда — любая возрастающая функция, образует иерархию быстрых итераций.
Системы фундаментальных последовательностей[]
Смотрите также: Список систем фундаментальных последовательностей
Иерархия Вайнера[]
Определения быстрорастущей иерархии и выбор фундаментальных систем последовательностей различаются у разных авторов, поэтому в целом проблематично говорить о быстрорастущей иерархии. Однако наиболее известной БРИ является иерархия Вайнера, которая имеет и систему ФП, определённую следующим образом:
(где с n копиями )
тогда и только тогда, когда является предельным ординалом
, где
(альтернативно )
(альтернативно )
Например, основная последовательность для — . Когда авторы без пояснений говорят о "быстрорастущей иерархии", обычно имеется в виду иерархия Вайнера.
Известно, что функции в иерархии Вайнера вычислимы, поскольку вся система может быть закодирована в ординальной нотации, связанной с итерированной нормальной формой Кантора с дополнительными структурами.
Иерархия Веблена[]
Каждый ненулевой ординал может быть однозначно записан в вариации нормальной формы Кантора от Веблена:
, где является функцией иерархии Веблена, и каждый ,
Для предельных ординалов , записанных в вариации нормальной формы Кантора от Веблена, фундаментальные последовательности для иерархии Веблена определяются следующим образом:
и
, где обозначает итерацию функции
для предельного ординала
для предельного ординала
для предельного ординала
Функция Веблена может быть представлена как функция с двумя аргументами .
Примечание: , , и
Известно, что функции в иерархии Веблена вычислимы, поскольку вся система может быть закодирована в ординальной нотации, связанной с Веблена с дополнительными конструкциями.
Иерархия Бухгольца[]
В Результат независимости для Уилфрид Бухгольц обсуждает ординальную иерархию иерархию, где , — функция свёртывания ординала Бухгольца и — ординал Такеути-Фефермана-Бухгольца. Известно, что функции в иерархии Бухгольца вычислимы, поскольку вся система может быть закодирована в ординальной нотации Бухгольца с дополнительными структурами.
Другие иерархии[]
Мы можем легко заменить иерархию Вайнера другой, например, иерархией, которая работает для гораздо более крупных ординалов, таких как малый ординал Веблена или ординал Такеути-Фефермана-Бухгольца. Пока определены фундаментальные последовательности, которые могут расширить БРИ до произвольного счётного ординала. Однако невозможно создать эффективную систему, работающую для всех счётных ординалов, поскольку система фундаментальных последовательностей до была бы неконструктивной.
Выбор фундаментальных последовательностей — непростая задача, поскольку некоторые варианты выбора могут привести к патологическим иерархиям, где не обязательно подразумевает (где означает возможное доминирование). В статье 1976 года Диана Шмидт доказала теорему, которая полезна для выявления патологических иерархий и защиты от них.[4] Учитывая систему фундаментальных последовательностей, определите и . Система фундаментальных последовательностей является созданной, если для всех и для некоторого . Шмидт по сути показала, что построенная система фундаментальных последовательностей гарантирует, что все монотонно возрастают и что (хотя в доказательстве предполагается, что данная иерархия удовлетворяет условию , что неверно в быстрорастущей иерархии и легко изменить доказательство, чтобы оно стало применимым к быстрорастущей иерархии).
Можно определить быстрорастущую иерархию для всех рекурсивных и даже для нерекурсивных счётных ординалов. Однако определения обязательно будут нерекурсивными, что значительно усложнит анализ. Насколько нам известно, не проводилось исследований по созданию нерекурсивных быстрорастущих иерархий.
Во многих случаях вычислимость быстрорастущей иерархии для данной системы фундаментальных последовательностей нетривиальна, хотя гугологи часто считают её тривиальной, не разбираясь в вопросе.
Значения[]
Ниже приведены некоторые функции в иерархии Вайнера и иерархии Веблена в сравнении с другими гугологическими нотациями.
Есть несколько вещей, на которые следует обратить внимание:
Отношения, обозначенные , выполняются для достаточно больших , не обязательно всех (т.е. в конечном итоге доминирует над ).
В этом разделе мы используем несколько систем фундаментальных последовательностей, например, для нормальной формы Кантора и для функции Веблена. Поскольку они явно не указаны, мы не знаем, какие системы подходят для этих результатов. Поэтому будьте осторожны, чтобы вычисления не сработали при попытке применить их к конкретной системе.
Расширение иерархии Гжегорчика[]
Иерархия Гжегорчика — иерархия функций (в частности, она содержит все и только примитивно-рекурсивные функции), классифицированных по скорости роста. Хотя "расширенная иерархия Гжегорчика" иногда может быть альтернативным названием быстрорастущей иерархии, её также можно использовать как способ строгой классификации функций на основе скорости их роста и системы фундаментальных последовательностей.
Исторические вариации[]
Версия Лоба и Вайнера 1970 (оригинал)[]
Исходные быстрорастущие функции, определенные Мартином Лобом и Стенли С. Вайнером в 1970 году,[5] отличался от известной формы.
Ниже приводится определение, данное в статье 1970 года:
,
,
для предельного ординала ,
Здесь для предельного ординала , определяется как
,
где — μ оператор, который возвращает наименьшее n, удовлетворяющее , если оно существует. То есть — наименьшее число такое, что для всех и больших, чем .
Обратите внимание, что нетривиально, и это потому, что требуется в статье 1970 года.
В продолжении статьи 1970 года[6] Лоб и Вайнер показали , если фундаментальная последовательность установлена определённым образом (это более сложный способ и сейчас он не используется).
Версия Вайнера 1972[]
В 1972 году Вайнер использовал более усовершенствованную версию быстрорастущей функции:
,
,
, для ,
, для предельного ординала ,
где — итераций , то есть , применяя раз.
На этот раз фундаментальная последовательность установлена такой же, как в иерархии Вайнера, за исключением .
Версия Кетона и Соловея 1981[]
Известная форма была представлена в 1981 году Юсси Кетоненом и Робертом Соловеем.[7]
Наконец мы получили простую и быстрорастущую последовательность функций.
160 — целое число, равное f2(5), а также количеству возможных ходов коня в мини-шахматах 6×6.
DeepLineMadom называет это число унуголквинплекс и унуголквинтиплекс и оно равно 10[1]10[1]10[1]10[1]10[1]10[1]100 в его нотации массива.[9]
212 — первое число n, такое, что f2(n) больше, чем первый неканоническый -иллион.
Изотоп радий-212 — единственный нуклид радия с отрицательным избытком массы. Никакие более тяжелые элементы не имеют изотопов с отрицательным избытком массы.
384 — целое число, равное f2(6), 8!! и 12!!!!, а также количеству дней в некоторые годы в еврейском календаре.
896 — целое число, равное f2(7), а также количеству возможных ходов ладьи в шахматах.
1,651 — наименьшее число n, для которого f2(n) больше, чем гуголдинг. Его простая факторизация равна 13×127.
Оно также используется в серии конфлурфин PlantStar.[10]
10,240 — целое число, равное f2(10), которое Денис Максудов называет 'балум'.
491,520 — целое число, равное f2(15). Кроме того, у него есть несвязанное свойство: поскольку оно равно 6C4 × 224−1, оно также появляется в комбинаторике, связанной с чемпионатом Европы по футболу.
↑Диана Шмидт, Построенные системы фундаментальных последовательностей и иерархий теоретико-числовых функций, Archiv für mathematische Logik und Grundlagenforschung 18 (1976), с. 47–53.
↑Лоб, М.Х. и Вайнер, С.С.: Иерархии теоретико-числовых функций Ⅰ. Archiv für mathematische Logik und Grundlagenforschung, том 13, выпуски 1–2 (1970). с. 39–51. doi:10.1007/BF01967649
↑Лоб М.Х. и Вайнер С.С.: Иерархии теоретико-числовых функций Ⅱ. Archiv für mathematische Logik und Grundlagenforschung, том 13, выпуск 3–4, с. 97–113 (1970). doi:10.1007/BF01973616
↑Кетонен, Юсси и Соловей, Роберт: Быстрорастущие функции Рамсея. Анналы математики, Vol. 113, № 2, с. 267–314 (1981). doi:10.2307/2006985. JSTOR:[1]