Primitivně rekurzivní funkce

Z Wikipedie, otevřené encyklopedie

Pojmem primitivně rekurzivní funkce (PRF) se v teorii vyčíslitelnosti označuje třída v jistém smyslu „jednoduchých“ funkcí. Jejich rozšířením je třída částečně rekurzivních funkcí (ČRF).

Obsah

1 Definice
2 Příklady
3 Univerzální PRF
4 Podívejte se také na

[editovat] Definice

[editovat] 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í.

[editovat] 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

μ z (f) = h

je n-ární primitivně rekurzivní funkce, kde $h(x_1, \ldots, x_n)\downarrow\;$ a $h(x_1, \ldots, x_n) \simeq z$ , jestliže $f(x_1, \ldots, x_n)\downarrow\;$ a $f(x_1, \ldots, x_n) = 0$

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

[editovat] 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.

[editovat] 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 tzv. Ackermannova funkce.

[editovat] Univerzální PRF

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

důkaz sporem: Nechť U(x, x) je univerzální PRF, která počítá výstup x-té PRF na vstupu x. 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ý.