Částečně rekurzivní funkce: Porovnání verzí
Smazaný obsah Přidaný obsah
m Zasataralá údržbová šablona; kosmetické úpravy |
|||
Řádek 16: | Řádek 16: | ||
* libovolná ČRF, která je někde nedefinována |
* libovolná ČRF, která je někde nedefinována |
||
* <s>[[McCarthyho funkce 91]] </s> (viz [[:en:McCarthy 91 function]]) |
* <s>[[McCarthyho funkce 91]] </s> (viz [[:en:McCarthy 91 function]]) |
||
{{Interwiki konflikt}} |
|||
[[Kategorie:Vyčíslitelnost]] |
[[Kategorie:Vyčíslitelnost]] |
Verze z 30. 5. 2016, 11:07
Čá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
- 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)