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

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

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

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

Визначення

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

$\begin{array}{ccc}{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.

Визначимо класи ієрархії ${ℰ}^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 в ${ℰ}^n$, тоді $f(\overline{u})=h(g_1(\overline{u}),g_2(\overline{u}),\dots ,g_m(\overline{u}))$ теж в ${ℰ}^n$); та
6. результат обмеженої (примітивної) рекурсії застосований до функцій класу, (якщо g, h, j в ${ℰ}^n$ та $f(t,\overline{u})\le j(t,\overline{u})$ для всіх t та $\overline{u}$, а також $f(0,\overline{u})=g(\overline{u})$ та $f(t+1,\overline{u})=h(t,\overline{u},f(t,\overline{u}))$, тоді f також в ${ℰ}^n$).

Тобто, ${ℰ}^n$ є замиканням множини $B_n=\{Z,S,(p_i^m{)}_{i\le m},E_k:k<n\}$ відносно композиції та обмеженої рекурсії.

Властивості

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

${ℰ}^0\subseteq {ℰ}^1\subseteq {ℰ}^2\subseteq \cdots$

тому що вони є замиканнями відповідних множин $B_0\subseteq B_1\subseteq B_2\subseteq \cdots$.

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

${ℰ}^0⊊{ℰ}^1⊊{ℰ}^2⊊\cdots$

тому що гіпероператор $H_n$ в ${ℰ}^n$ але не в ${ℰ}^{n-1}$.

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

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

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

За визначенням ${ℰ}^n\subseteq 𝖯𝖱$) та

$\bigcup _n{ℰ}^n\subseteq 𝖯𝖱$

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

$\bigcup _n{ℰ}^n=𝖯𝖱$

Множини ${ℰ}^0,{ℰ}^1-{ℰ}^0,{ℰ}^2-{ℰ}^1,\dots ,{ℰ}^n-{ℰ}^{n-1},\dots$ поділяють множину PR.

Розширення

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

Існує розширення ієрархії на трансфінітні ординали, що називається Шаблон:Li.