Primitivně rekurzivní funkce

Z Wikipedie, otevřené encyklopedie

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

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

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

  • nulová funkce
  • následník
  • projekce (vydělení j-tého z n argumentů)

Označení 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 je n-ární primitivně rekurzivní funkce, kde a
  • substituce
    • je-li f m-ární PRF a
    • jsou-li n-ární PRF
pak je n-ární primitivně rekurzivní funkce, kde
  • minimalizace
    • je-li f (n + 1)-ární PRF
pak je n-ární funkce, , pokud a zároveň

Označení   znamená, že funkce f je pro argumenty definována (neboli konverguje). Pokud by funkce pro tyto argumenty divergovala (nebyla definována), píšeme .

Třída PRF[editovat | editovat zdroj]

Třída primitivně rekurzivních funkcí je nejmenší třídou funkcí , 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 Ackermannova funkce.

Univerzální PRF[editovat | editovat zdroj]

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 pro nějaké . Nyní přichází klíčový krok důkazu, kdy za x dosadíme (tzn. Cantorova diagonální metoda) a dostáváme , což je spor. Předpoklad, že U je primitivně rekurzivní funkce, byl tedy chybný.