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

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

Иерархия Гжегорчика (, Польское произношение: ), названный в честь польского логика Анджея Гжегорчика, иерархия функций, используемых в теории вычислимости (Wagner and Wechsung 1986: 43). Каждая функция в иерархии Гжегорчика является примитивной рекурсивной функцией, и каждая примитивно рекурсивная функция появляется в иерархии на каком-то уровне. Иерархия имеет дело со скоростью, с которой значения функций растут; интуитивно понятно, что функции на более низком уровне иерархии растут медленнее, чем функции на более высоких уровнях.

Содержание

1 Определение
2 Свойства
3 Отношение к примитивным рекурсивным функциям
4 Расширения
5 См. Также
6 Примечания
7 Ссылки

Определение

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

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

Ekдля k < n
нулевая функция (Z (x) = 0);
функция-преемник (S (x) = x + 1);
функции проекции ( $pim (t 1, t 2,…, tm) = ti {\ displaystyle p_ {i} ^ {m} (t_ {1}, t_ {2}, \ dots, t_ { m}) = t_ {i}}$ $p_ {i} ^ {m} (t_ {1}, t_ {2}, \ dots, t_ {m}) = t_ {i}$ );
(обобщенная) композиция функций в наборе (если h, g 1, g 2,... и g m находятся в $E n {\ displaystyle {\ mathcal {E}} ^ {n}}$ ${\ mathcal {E}} ^ {n}$ , затем $f (u ¯) знак равно час (g 1 (u ¯), g 2 (u ¯),…, gm (u ¯)) {\ displaystyle f ({\ bar {u}}) = h (g_ {1} ({\ bar { u}}), g_ {2} ({\ bar {u}}), \ dots, g_ {m} ({\ bar {u}}))}$ $f ({\ bar {u }}) = h (g_ {1} ({\ bar {u}}), g_ {2} ({\ bar {u}}), \ dots, g_ {m} ({\ bar {u}}))$ тоже); и
результаты ограниченной (примитивной) рекурсии, примененные к функциям в наборе (если g, h и j находятся в $E n {\ displaystyle {\ mathcal {E}} ^ {n}}$ ${\ mathcal {E}} ^ {n}$ и $е (t, u ¯) ≤ j (t, u ¯) {\ displaystyle f (t, {\ bar {u}}) \ leq j (t, {\ bar {u }})}$ $f (t, {\ bar {u}}) \ leq j (t, {\ bar {u}})$ для всех t и $u ¯ {\ displaystyle {\ bar {u}}}$ ${\ bar {u}}$ и далее $f (0, u ¯) = g (u ¯) {\ displaystyle f (0, {\ bar {u}}) = g ({\ bar {u}})}$ $f (0, {\ bar {u}}) = g ({\ bar {u}})$ и $f (t + 1, u ¯) = h (t, u ¯ е (т, и ¯)) {\ Displaystyle е (т + 1, {\ бар {u}}) = ч (т, {\ бар {u}}, е (т, {\ бар {u}})))}$ $f (t + 1, {\ bar {u}}) = h (t, { \ bar {u}}, f (t, {\ bar {u}}))$ , тогда f также находится в $E n {\ displaystyle {\ mathcal {E}} ^ {n}}$ ${\ mathcal {E}} ^ {n}$ )

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

Свойства

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

E 0 ⊆ E 1 ⊆ E 2 ⊆ ⋯ {\ displaystyle {\ mathcal {E}} ^ {0} \ substeq {\ mathcal {E}} ^ {1} \ substeq {\ mathcal {E}} ^ {2} \ substeq \ cdots}

{\ mathcal {E}} ^ {0} \ substeq {\ mathcal {E}} ^ {1} \ substeq {\ mathcal {E}} ^ {2} \ substeq \ cdots

, потому что они являются замыканиями над $B n {\ displaystyle B_ {n}}$ $B_{n}$ и $B 0 ⊆ B 1 ⊆ B 2 ⊆ ⋯ {\ displaystyle B_ {0} \ substeq B_ {1} \ substeq B_ {2} \ substeq \ cdots}$ $B_ {0} \ substeq B_ {1} \ substeq B_ {2} \ substeq \ cdots$ .

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

E 0 ⊊ E 1 ⊊ E 2 ⊊ ⋯ {\ displaystyle {\ mathcal {E}} ^ {0} \ subsetneq {\ mathcal {E}} ^ {1} \ subsetneq {\ mathcal {E }} ^ {2} \ subsetneq \ cdots}

{\ mathcal {E}} ^ {0} \ subsetneq {\ mathcal {E}} ^ {1} \ subsetneq {\ mathcal {E}} ^ {2} \ subsetneq \ cdots

, потому что гипероперация $H n {\ displaystyle H_ {n}}$ $H_{n}$ находится в $E n {\ displaystyle {\ mathcal {E}} ^ {n}}$ ${\ mathcal {E}} ^ {n}$ , но не в $E n - 1 {\ displaystyle {\ mathcal {E}} ^ {n-1}}$ ${\ mathcal {E}} ^ {{n-1}}$ .

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

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

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

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

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

⋃ n E n ⊆ PR {\ displaystyle \ bigcup _ {n} {{\ mathcal {E}} ^ {n}} \ substeq {\ mathsf {PR}}}

{\ displaystyle \ bigcup _ {n } {{\ mathcal {E}} ^ {n}} \ substeq {\ mathsf {PR}}}

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

⋃ n E n = PR {\ displaystyle \ bigcup _ {n} {{\ mathcal {E}} ^ {n}} = {\ mathsf {PR}}}

{\ displaystyle \ bigcup _ {n} {{\ mathcal {E}} ^ {n}} = {\ mathsf {PR}}}

и наборы $E 0, E 1 - E 0, E 2 - E 1,…, E n - E n - 1,… {\ 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}$ ${\ 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.

Расширения

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

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

См. Также

Примечания

Ссылки

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