Cesko.wiki Částečně rekurzivní funkce
Author
Albert FloresČá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. +more 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. +more 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