Ієрархія Гжегорчика — ієрархія функцій в теорії обчислюваності, названа іменем польського логіка .
В цій ієрархії присутні всі примітивно рекурсивні функції і тільки вони.
Ієрархія розділяє їх на рівні по швидкості зростання. Функції на нижчих рівнях зростають повільніше ніж на вищих.
Визначення Визначимо нескінченну множину функцій Ei, де i натуральне число:
— додавання, — многочлен другого степеня. Для всіх n > 1, — ітерація функції для 2.
Визначимо класи ієрархії , що включатимуть такі функції: Ek для k < n нульова функція (Z(x) = 0); функція-наступник (S(x) = x + 1); функція проектування (); (узагальнена) композиція функцій (якщо h, g1, g2, ... gm в , тоді теж в ); та результат обмеженої (примітивної) рекурсії застосований до функцій класу, (якщо g, h, j в та для всіх t та , а також та , тоді f також в ).
Тобто, є замиканням множини відносно композиції та обмеженої рекурсії.
Властивості Множини утворюють ієрархію
тому що вони є замиканнями відповідних множин .
Ніде немає рівності
тому що гіпероператор в але не в .
включає функції x+1, x+2, ... добавляє функції x+y, 4x, ... добавляє такі добутки як xy, x4 добавляє такі піднесення до степеня xy, 222x і рівний класу ELEMENTARY. добавляє тетрації, наступні класи по аналогії.
Примітивні рекурсивні функції Визначення співпадає з визначенням примітивно рекурсивних функцій, за винятком того, що рекурсія обмежена ( для j в ) та функції явно включені в . Тому ця ієрархія розділяє силу примітивної рекурсії на різні рівні.
За визначенням ) та
Також можна показати, що довільна функція з PR знаходиться на деякому рівні ієрархії, тому
Множини поділяють множину PR.
Розширення Існує схожа класифікація на основі програми LOOP.
Існує розширення ієрархії на трансфінітні ординали, що називається .