Ієрархія Гжегорчика

Ієрархія Гжегорчика — ієрархія функцій в теорії обчислюваності, названа іменем польського логіка Анджея Гжегорчика.

В цій ієрархії присутні всі примітивно рекурсивні функції і тільки вони.

Ієрархія розділяє їх на рівні по швидкості зростання. Функції на нижчих рівнях зростають повільніше ніж на вищих.

Визначення

Визначимо нескінченну множину функцій E_i, де i натуральне число:

${\begin{array}{lcl}E_{0}(x,y)&=&x+y\\E_{1}(x)&=&x^{2}+2\\E_{n+2}(0)&=&2\\E_{n+2}(x+1)&=&E_{n+1}(E_{n+2}(x))\\\end{array}}$

$E_{0}$ — додавання, $E_{1}$ — многочлен другого степеня. Для всіх n > 1, $E_{n}(x)=E_{n-1}^{x}(2)$ — ітерація функції $E_{n-1}$ для 2.

Визначимо класи ієрархії ${\mathcal {E}}^{n}$, що включатимуть такі функції:

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

Тобто, ${\mathcal {E}}^{n}$ є замиканням множини $B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}$ відносно композиції та обмеженої рекурсії.

Властивості

Множини утворюють ієрархію

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

тому що вони є замиканнями відповідних множин $B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots$.

Ніде немає рівності

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

тому що гіпероператор $H_{n}$ в ${\mathcal {E}}^{n}$ але не в ${\mathcal {E}}^{n-1}$.

• ${\mathcal {E}}^{0}$ включає функції x+1, x+2, ...
• ${\mathcal {E}}^{1}$ добавляє функції x+y, 4x, ...
• ${\mathcal {E}}^{2}$ добавляє такі добутки як xy, x⁴
• ${\mathcal {E}}^{3}$ добавляє такі піднесення до степеня x^y, 2^22x і рівний класу ELEMENTARY.
• ${\mathcal {E}}^{4}$ добавляє тетрації, наступні класи по аналогії.

Примітивні рекурсивні функції

Визначення ${\mathcal {E}}^{n}$ співпадає з визначенням примітивно рекурсивних функцій, за винятком того, що рекурсія обмежена ($f(t,{\bar {u}})\leq j(t,{\bar {u}})$ для j в ${\mathcal {E}}^{n}$) та функції $(E_{k})_{k<n}$ явно включені в ${\mathcal {E}}^{n}$. Тому ця ієрархія розділяє силу примітивної рекурсії на різні рівні.

За визначенням ${\mathcal {E}}^{n}\subseteq {\mathsf {PR}}$) та

$\bigcup _{n}{{\mathcal {E}}^{n}}\subseteq {\mathsf {PR}}$

Також можна показати, що довільна функція з PR знаходиться на деякому рівні ієрархії, тому

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

Множини ${\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.

== Розширення ==

Існує схожа класифікація на основі програми LOOP.

Існує розширення ієрархії на трансфінітні ординали, що називається швидко-зростаюча ієрархія.