Vypočitatelná funkce (nebo rekurzivní funkce ) je semi-vypočitatelná funkce (nebo částečné rekurzivní funkce ), která je také celkem , to znamená, že je definován po celé své doméně. Jedná se o funkce počítané „ukončovacím“ Turingovým strojem .
Vypočitatelná funkce nemusí být nutně „fyzicky vypočítatelná“, například pokud doba jejího provedení překročí několik miliard let.
Nejjednodušší příklady vypočítatelných funkcí jsou konstantní funkce . Důsledkem principu vyloučené třetiny je pak to, že konstantní funkce, která s celým číslem spojuje 1, pokud je Goldbachova domněnka pravdivá, a 0, pokud je nepravdivá, je vypočítatelná, i když dnes nevíme, zda je domněnka pravdivá. To ukazuje, jak aplikace tohoto principu ničí jakoukoli intuitivní představu o vypočítatelnosti.