Иерархия Гжегорчика - Grzegorczyk hierarchy

В Иерархия Гжегорчика (/ɡрɛˈɡɔːrtʃək/, Польское произношение:[ɡʐɛˈɡɔrt͡ʂɨk]), названный в честь польского логика Анджей Гжегорчик, представляет собой иерархию функций, используемых в теория вычислимости (Вагнер и Вексунг 1986: 43). Каждый функция в иерархии Гжегорчика является примитивная рекурсивная функция, и каждая примитивная рекурсивная функция появляется в иерархии на каком-то уровне. Иерархия имеет дело со скоростью, с которой значения функций растут; интуитивно понятно, что функции на более низком уровне иерархии растут медленнее, чем функции на более высоких уровнях.

Определение

Сначала введем бесконечный набор функций, обозначенных E_я для некоторого натурального числа я. Мы определяем ${displaystyle E_{0}(x,y)=x+y}$ и ${displaystyle E_{1}(x)=x^{2}+2}$. Т.е., E₀ - функция сложения, а E₁ - унарная функция, которая возводит свой аргумент в квадрат и добавляет два. Затем для каждого п больше 1, определим ${displaystyle E_{n}(x)=E_{n-1}^{x}(2)}$, т.е. Икс-го повторять из ${displaystyle E_{n-1}}$ оценен в 2.

По этим функциям мы определяем иерархию Гжегорчика. ${displaystyle {mathcal {E}}^{n}}$, то п-й набор в иерархии содержит следующие функции:

1. E_k за k < п
2. нулевая функция (Z(Икс) = 0);
3. то функция преемника (S(Икс) = Икс + 1);
4. то функции проекции (${displaystyle p_{i}^{m}(t_{1},t_{2},dots ,t_{m})=t_{i}}$);
5. (обобщенный) композиции функций в наборе (если час, грамм₁, грамм₂, ... и грамм_м находятся в ${displaystyle {mathcal {E}}^{n}}$, тогда ${displaystyle f({ar {u}})=h(g_{1}({ar {u}}),g_{2}({ar {u}}),dots ,g_{m}({ar {u}}))}$ тоже)^{[примечание 1]}; и
6. результаты ограниченной (примитивной) рекурсии, примененные к функциям в наборе, (если грамм, час и j находятся в ${displaystyle {mathcal {E}}^{n}}$ и ${displaystyle f(t,{ar {u}})leq j(t,{ar {u}})}$ для всех т и ${displaystyle {ar {u}}}$, и далее ${displaystyle f(0,{ar {u}})=g({ar {u}})}$ и ${displaystyle f(t+1,{ar {u}})=h(t,{ar {u}},f(t,{ar {u}}))}$, тогда ж в ${displaystyle {mathcal {E}}^{n}}$ также)^{[примечание 1]}

Другими словами, ${displaystyle {mathcal {E}}^{n}}$ это закрытие набора ${displaystyle B_{n}={Z,S,(p_{i}^{m})_{ileq m},E_{k}:k<n}}$ в отношении композиции функций и ограниченной рекурсии (как определено выше).

Характеристики

Эти наборы четко образуют иерархию

${displaystyle {mathcal {E}}^{0}subseteq {mathcal {E}}^{1}subseteq {mathcal {E}}^{2}subseteq cdots }$

потому что они закрывают ${displaystyle B_{n}}$'песок ${displaystyle B_{0}subseteq B_{1}subseteq B_{2}subseteq cdots }$.

Это строгие подмножества (Rose 1984; Gakwaya 1997). Другими словами

${displaystyle {mathcal {E}}^{0}subsetneq {mathcal {E}}^{1}subsetneq {mathcal {E}}^{2}subsetneq cdots }$

поскольку гипероперация ${displaystyle H_{n}}$ в ${displaystyle {mathcal {E}}^{n}}$ но не в ${displaystyle {mathcal {E}}^{n-1}}$.

• ${displaystyle {mathcal {E}}^{0}}$ включает такие функции, как Икс+1, Икс+2, ...
• ${displaystyle {mathcal {E}}^{1}}$ предоставляет все дополнительные функции, такие как Икс+у, 4Икс, ...
• ${displaystyle {mathcal {E}}^{2}}$ предоставляет все функции умножения, такие как ху, Икс⁴
• ${displaystyle {mathcal {E}}^{3}}$ предоставляет все функции возведения в степень, такие как Икс^у, 2^22Икс, и именно элементарные рекурсивные функции.
• ${displaystyle {mathcal {E}}^{4}}$ предоставляет все тетрация функции и так далее.

Примечательно, что как функция ${displaystyle U}$ и характеристическая функция предиката ${displaystyle T}$ от Теорема Клини о нормальной форме определены таким образом, что они лежат на уровне ${displaystyle {mathcal {E}}^{0}}$ иерархии Гжегорчика. Это означает, в частности, что каждое рекурсивно перечислимое множество перечислимо некоторым ${displaystyle {mathcal {E}}^{0}}$-функция.

Отношение к примитивным рекурсивным функциям

Определение ${displaystyle {mathcal {E}}^{n}}$ такой же, как у примитивные рекурсивные функции, PR, за исключением того, что рекурсия ограничено (${displaystyle f(t,{ar {u}})leq j(t,{ar {u}})}$ для некоторых j в ${displaystyle {mathcal {E}}^{n}}$) и функции ${displaystyle (E_{k})_{k<n}}$ явно включены в ${displaystyle {mathcal {E}}^{n}}$. Таким образом, иерархию Гжегорчика можно рассматривать как способ предел сила примитивной рекурсии на разных уровнях.

Из этого факта ясно, что все функции на любом уровне иерархии Гжегорчика являются примитивными рекурсивными функциями (т.е. ${displaystyle {mathcal {E}}^{n}subseteq {mathsf {PR}}}$) и поэтому:

${displaystyle igcup _{n}{{mathcal {E}}^{n}}subseteq {mathsf {PR}}}$

Также можно показать, что все примитивные рекурсивные функции находятся на каком-то уровне иерархии (Rose 1984; Gakwaya 1997), таким образом

${displaystyle igcup _{n}{{mathcal {E}}^{n}}={mathsf {PR}}}$

и наборы ${displaystyle {mathcal {E}}^{0},{mathcal {E}}^{1}-{mathcal {E}}^{0},{mathcal {E}}^{2}-{mathcal {E}}^{1},dots ,{mathcal {E}}^{n}-{mathcal {E}}^{n-1},dots }$ раздел набор примитивных рекурсивных функций, PR.

Расширения

Основная статья: Быстрорастущая иерархия

Иерархию Гжегорчика можно расширить до трансфинитный порядковые. Такие расширения определяют быстрорастущая иерархия. Для этого производящие функции ${displaystyle E_{alpha }}$ должны быть рекурсивно определены для предельных ординалов (обратите внимание, что они уже были рекурсивно определены для последующих порядковых номеров отношением ${displaystyle E_{alpha +1}(n)=E_{alpha }^{n}(2)}$). Если есть стандартный способ определения основная последовательность ${displaystyle lambda _{m}}$, чей предельный порядковый номер является ${displaystyle lambda }$, то производящие функции можно определить ${displaystyle E_{lambda }(n)=E_{lambda _{n}}(n)}$. Однако это определение зависит от стандартного способа определения фундаментальной последовательности. Роуз (1984) предлагает стандартный способ для всех ординалов α < ε₀.

Первоначальное расширение было связано с Мартин Лёб и Стэн С. Уэйнер (1970) и иногда называют Иерархия Лёба – Вайнера.

Смотрите также

• НАЧАЛЬНЫЙ
• Порядковый анализ

Примечания

1. Здесь ${displaystyle {ar {u}}}$ представляет кортеж входов в ж. Обозначение ${displaystyle f({ar {u}})}$ Значит это ж берет произвольный количество аргументов и если ${displaystyle {ar {u}}=(x,y,z)}$, тогда ${displaystyle f({ar {u}})=f(x,y,z)}$. В обозначениях ${displaystyle f(t,{ar {u}})}$, первый аргумент, т, указывается явно, а остальные как произвольный кортеж ${displaystyle {ar {u}}}$. Таким образом, если ${displaystyle {ar {u}}=(x,y,z)}$, тогда ${displaystyle f(t,{ar {u}})=f(t,x,y,z)}$. Эта нотация позволяет определять композицию и ограниченную рекурсию для функций, ж, любого количества аргументов.

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

• Брейнерд, У.С., Ландвебер, Л.Х. (1974), Теория вычислений, Wiley, ISBN  0-471-09585-0
• Cichon, E.A .; Вайнер, С. С. (1983), "Медленнорастущие и иерархии Гжегорчика", Журнал символической логики, 48 (2): 399–408, Дои:10.2307/2273557, ISSN  0022-4812, МИСТЕР  0704094
• Gakwaya, J.–S. (1997), Обзор иерархии Гжегорчика и ее расширения с помощью модели вычислимости BSS
• Гжегорчик, А (1953). «Некоторые классы рекурсивных функций» (PDF). Rozprawy matematyczne. 4: 1–45.
• Löb, M.H .; Вайнер, С.С. (1970). "Иерархии теоретико-числовых функций I, II: поправка". Archiv für Mathematische Logik und Grundlagenforschung. 14: 198–199. Дои:10.1007 / bf01991855.
• Роуз, Е.П., Субрекурсия: функции и иерархии, Oxford University Press, 1984. ISBN  0-19-853189-3
• Вагнер, К. и Вексунг, Г. (1986), Вычислительная сложность, Математика и ее приложения v. 21. ISBN  978-90-277-2146-4