Částečně rekurzivní funkce

Z Wikipedie, otevřené encyklopedie

Částečně rekurzivní funkce (ČRF) je termín, kterým se v teorii vyčíslitelnosti označují funkce v jistém smyslu „složitější“ než tzv. primitivně rekurzivní funkce.

Definice[editovat | editovat zdroj]

Axiomy a operátory jsou stejné jako u primitivně rekurzivních funkcí. Třída ČRF je pak definovaná jako nejmenší třída funkcí, která obsahuje axiomy a je uzavřená na všechny tři operátory, tedy primitivní rekurzi, substituci i minimalizaci. Právě operátorem minimalizace se ČRF liší od PRF – zavádí totiž do výpočtu funkce potenciálně nekonečný cyklus.

Vlastnosti[editovat | editovat zdroj]

  • částečně rekurzivní funkce nejsou obecně definovány pro každý vstup – pokud je např. hodnota f(x) nedefinována, říkáme, že funkce f v bodě x diverguje a píšeme obvykle
  • podmnožina všude definovaných ČRF se nazývá třída obecně rekurzivních funkcí (ORF) , také třída totálních rekurzivních funkcí či jen rekurzivních funkcí
  • platí, že PRF je vlastní podmnožinou ORF, a ta je vlastní podmnožinou ČRF
  • existuje tzv. univerzální částečně rekurzivní funkce, která kromě vlastních argumentů dostává ještě index ČRF (tzv. Gödelovo číslo), jejíž hodnotu při daných argumentech vyčísluje. Tato univerzální funkce je ve smyslu výpočetní síly ekvivalentní s Turingovým strojem

Příklady[editovat | editovat zdroj]

Tyto funkce jsou částečně, ale ne primitivně rekurzivní:

  • Ackermannova funkce
  • univerzální částečně rekurzivní funkce (vzpomenutá výše)
  • libovolná ČRF, která je někde nedefinována