Částečně rekurzivní funkce: Porovnání verzí

→‎Vlastnosti: doplnění
(→‎Vlastnosti: doplnění)
== 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>
* [[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 [[Turingův stroj|Turingovým strojem]]
3 556

editací