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

[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 Rn(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, z)\downarrow\; a f(x_1, \ldots, x_n, z) = 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\;.

[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é x0. Nyní přichází klíčový krok důkazu, kdy za x dosadíme x0 (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ý.

[editovat] Podívejte se také na