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

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

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

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

Визначення

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

${\displaystyle {\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}}}$

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

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

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

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

Властивості

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

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

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

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

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

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

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

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

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

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

${\displaystyle \bigcup _{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.

Розширення

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

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