{{TIN064 Skripta}} Tato kapitola se věnuje zavedení a základním vlastnostem následujících tříd funkcí: částečně rekurzivní funkce (ČRF), obecně rekurzivní funkce (ORF) a primitivně rekurzivní funkce (PRF). Pokud tyto termíny slyšíte poprvé, doporučuji přečíst si nejprve <TIN064%20Úvod>.
Induktivní výstavba funkcí
Funkce budeme konstruovat induktivně: zavedeme si tři základní funkce (nulová, následník, <#vydělení%20j-té%20složky>) a pak tři operátory (substituce, primitivní rekurze, minimalizace). Operátor je taková "metafunkce" — na vstupu dostane jednu či více funkcí a na výstupu vrátí nějakou novou funkci.
Ke každé funkci, kterou takto zkonstruujeme, pak bude existovat její odvození, což je posloupnost funkcí, z nichž každá je buď základní funkcí nebo vznikla z předchozích funkcí pomocí nějakého operátoru.
Pokud vám to připomíná induktivní výstavbu důkazů v logice, tak si můžete připsat malé nevýznamné plus. Ano, základní funkce jsou paralelou k axiomům, operátory jsou paralelou k odvozovacím pravidlům (modus ponens,...) a odvození funkce je paralelou k odvození důkazu.