Ієрархія Гжегорчика — ієрархія функцій в теорії обчислюваності , названа іменем польського логіка Анджея Гжегорчика (інші мови) .
В цій ієрархії присутні всі примітивно рекурсивні функції і тільки вони.
Ієрархія розділяє їх на рівні по швидкості зростання. Функції на нижчих рівнях зростають повільніше ніж на вищих.
Визначимо нескінченну множину функцій Ei , де i натуральне число :
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 ) ) {\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}}} E 0 {\displaystyle E_{0}} — додавання , E 1 {\displaystyle E_{1}} — многочлен другого степеня. Для всіх n > 1, E n ( x ) = E n − 1 x ( 2 ) {\displaystyle E_{n}(x)=E_{n-1}^{x}(2)} — ітерація функції E n − 1 {\displaystyle E_{n-1}} для 2.
Визначимо класи ієрархії E n {\displaystyle {\mathcal {E}}^{n}} , що включатимуть такі функції:
Ek для k < n нульова функція (Z (x ) = 0); функція-наступник (S (x ) = x + 1); функція проектування ( p i m ( t 1 , t 2 , … , t m ) = t i {\displaystyle 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}} , тоді f ( u ¯ ) = h ( g 1 ( u ¯ ) , g 2 ( u ¯ ) , … , g m ( u ¯ ) ) {\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))} теж в E n {\displaystyle {\mathcal {E}}^{n}} ); та результат обмеженої (примітивної) рекурсії застосований до функцій класу, (якщо g , h , j в E n {\displaystyle {\mathcal {E}}^{n}} та f ( t , u ¯ ) ≤ j ( t , u ¯ ) {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})} для всіх t та u ¯ {\displaystyle {\bar {u}}} , а також f ( 0 , u ¯ ) = g ( u ¯ ) {\displaystyle f(0,{\bar {u}})=g({\bar {u}})} та f ( t + 1 , u ¯ ) = h ( t , u ¯ , f ( t , u ¯ ) ) {\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))} , тоді f також в E n {\displaystyle {\mathcal {E}}^{n}} ). Тобто, E n {\displaystyle {\mathcal {E}}^{n}} є замиканням множини B n = { Z , S , ( p i m ) i ≤ m , E k : k < n } {\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}} відносно композиції та обмеженої рекурсії.
Множини утворюють ієрархію
E 0 ⊆ E 1 ⊆ E 2 ⊆ ⋯ {\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots } тому що вони є замиканнями відповідних множин B 0 ⊆ B 1 ⊆ B 2 ⊆ ⋯ {\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots } .
Ніде немає рівності
E 0 ⊊ E 1 ⊊ E 2 ⊊ ⋯ {\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots } тому що гіпероператор H n {\displaystyle H_{n}} в E n {\displaystyle {\mathcal {E}}^{n}} але не в E n − 1 {\displaystyle {\mathcal {E}}^{n-1}} .
E 0 {\displaystyle {\mathcal {E}}^{0}} включає функції x +1, x +2, ... E 1 {\displaystyle {\mathcal {E}}^{1}} добавляє функції x +y , 4x , ... E 2 {\displaystyle {\mathcal {E}}^{2}} добавляє такі добутки як xy , x 4 E 3 {\displaystyle {\mathcal {E}}^{3}} добавляє такі піднесення до степеня x y , 222x і рівний класу ELEMENTARY . E 4 {\displaystyle {\mathcal {E}}^{4}} добавляє тетрації , наступні класи по аналогії. Визначення E n {\displaystyle {\mathcal {E}}^{n}} співпадає з визначенням примітивно рекурсивних функцій, за винятком того, що рекурсія обмежена ( f ( t , u ¯ ) ≤ j ( t , u ¯ ) {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})} для j в E n {\displaystyle {\mathcal {E}}^{n}} ) та функції ( E k ) k < n {\displaystyle (E_{k})_{k<n}} явно включені в E n {\displaystyle {\mathcal {E}}^{n}} . Тому ця ієрархія розділяє силу примітивної рекурсії на різні рівні.
За визначенням E n ⊆ P R {\displaystyle {\mathcal {E}}^{n}\subseteq {\mathsf {PR}}} ) та
⋃ n E n ⊆ P R {\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq {\mathsf {PR}}} Також можна показати, що довільна функція з PR знаходиться на деякому рівні ієрархії, тому
⋃ n E n = P R {\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 } поділяють множину PR.
== Розширення == Існує схожа класифікація на основі програми LOOP.
Існує розширення ієрархії на трансфінітні ординали , що називається швидко-зростаюча ієрархія (інші мови) .
Вважаються легкими Припускаються складними Вважаються складними Ієрархії
Основні Обернена до лівого аргументу Обернена до правого аргументу Класифікації