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

m
typo
(→‎Příklady: -přeškrtnutá funkce, tak je, či není?)
m (typo)
 
 
== Definice ==
[[Axiom]]y a [[operátor]]y 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čno|nekonečný]] [[cyklus (informatika)|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 <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