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