Částečně rekurzivní funkce

Čá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

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

čá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 $f(x)\uparrow$
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

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