Primitivně rekurzivní funkce

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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).

Definice[editovat | editovat zdroj]

Základní funkce (axiomy)[editovat | editovat zdroj]

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

  • 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 divergovala (nebyla pro tyto argumenty definována), píšeme f(x_1, \ldots, x_n, z)\uparrow\;.

Třída PRF[editovat | editovat zdroj]

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

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.

Univerzální PRF[editovat | editovat zdroj]

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ý.

Související články[editovat | editovat zdroj]