Primitivně rekurzivní funkce

Primitivně rekurzivní funkce (PRF) je v teorii vyčíslitelnosti v jistém smyslu „jednoduchá“ funkce. Jejím rozšířením je částečně rekurzivní funkce (ČRF).

Definice

Základní funkce (axiomy)

Všechny tři níže uvedené funkce jsou primitivně rekurzivní:

• nulová funkce

$\forall x\;o(x)\simeq 0$

• následník

$\forall x\;s(x)\simeq x+1$

• projekce (vydělení j-tého z n argumentů)

$\forall x\;\forall j\;\forall n\;I_{n}^{j}(x_{1},\ldots ,x_{n})\simeq x_{j}$

Označení $f(x)\simeq g(x)$ znamená, že pokud má alespoň jedna strana rovnice smysl (tzn. je definována), pak má smysl i druhá strana a hodnoty funkcí f a g v bodě x se rovnají.

Operátory

• primitivní rekurze:
  • je-li f (n - 1)-ární PRF a
  • g (n + 1)-ární PRF

pak $R_{n}(f,g)=h$ je n-ární primitivně rekurzivní funkce, kde $h(0,x_{2},\ldots ,x_{n})\simeq f(x_{2},\ldots ,x_{n})$ a $h(y+1,x_{2},\ldots ,x_{n})\simeq g(y,h(y,x_{2},\ldots ,x_{n}),x_{2},\ldots ,x_{n})$

• substituce
  • je-li f m-ární PRF a
  • jsou-li $g_{1},\ldots ,g_{m}$ n-ární PRF

pak $S_{n}^{m}(f,g_{1},\ldots ,g_{m})=h$ je n-ární primitivně rekurzivní funkce, kde $h(x_{1},\ldots ,x_{n})\simeq f(g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}))$

• minimalizace
  • je-li f (n + 1)-ární PRF

pak $\mu (f)$ je n-ární funkce, $\mu (f)(x_{1},\ldots ,x_{n})=z$, pokud $f(x_{1},\ldots ,x_{n},z)=0$ a zároveň $(\forall i<z)f(x_{1},\ldots ,x_{n},i)>0$

Označení $f(x_{1},\ldots ,x_{n},z)\downarrow \;$  znamená, že funkce f je pro argumenty $(x_{1},\ldots ,x_{n},z)$ definována (neboli konverguje). Pokud by funkce pro tyto argumenty divergovala (nebyla definována), píšeme $f(x_{1},\ldots ,x_{n},z)\uparrow \;$.

Třída PRF

Třída primitivně rekurzivních funkcí je nejmenší třídou funkcí $f:\mathbb {N} ^{k}\rightarrow \;\mathbb {N}$, která obsahuje axiomy a je uzavřená na operátory primitivní rekurze a substituce. Odvození funkce je pak konečná posloupnost funkcí, z nichž každá je buď axiom nebo vzniká z předchozích funkcí aplikací některého operátoru.

Zjednodušeně řečeno, primitivně rekurzivní funkce je taková, kterou lze zapsat jako počítačový program obsahující pouze konečné for cykly a žádné while cykly nebo skoky.

Primitivně rekurzivní predikát je takový, jehož charakteristická funkce je nějaká primitivně rekurzivní funkce.

Příklady

V podstatě všechny „klasické“ funkce (sčítání, odčítání, ale také například test prvočíselnosti) jsou primitivně rekurzivní. Příkladem funkce, která není primitivně rekurzivní, je Ackermannova funkce.

Univerzální PRF

Třída PRF má svoji univerzální funkci, ta ale sama do třídy PRF nepatří.

Důkaz sporem: Nechť U(x, y) je univerzální PRF, která počítá výstup x-té PRF na vstupu y. Pak U(x, x) + 1 je také PRF (použitím operátoru substituce a funkce následníka). Protože U je univerzální funkce, platí, že $U(x,x)+1\simeq U(x_{0},x)$ pro nějaké $x_{0}$. Nyní přichází klíčový krok důkazu, kdy za x dosadíme $x_{0}$ (tzn. Cantorova diagonální metoda) a dostáváme $U(x_{0},x_{0})+1\simeq U(x_{0},x_{0})$, což je spor. Předpoklad, že U je primitivně rekurzivní funkce, byl tedy chybný.