Čá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
• McCarthyho funkce 91 (viz en:McCarthy 91 function)