Částečně rekurzivní funkce: Porovnání verzí
Smazaný obsah Přidaný obsah
m robot přidal: he:פונקציה רקורסיבית |
→Vlastnosti: doplnění |
||
Řádek 6: | Řádek 6: | ||
== Vlastnosti == |
== 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 <math>f(x)\uparrow</math> |
* čá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 <math>f(x)\uparrow</math> |
||
* [[podmnožina]] všude definovaných ČRF se nazývá třída '''obecně rekurzivních funkcí''' ('''ORF''') |
* [[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 |
* 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 [[Turingův stroj|Turingovým strojem]] |
* 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 [[Turingův stroj|Turingovým strojem]] |
Verze z 17. 2. 2007, 00:57
Čá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, 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í: