Les fonctions partielles récursives correspondent aux fonctions calculées par une machine de Turing. Selon la thèse de Church la classe des fonctions partielles récursives est exactement l'ensemble des fonctions numériques pouvant être décrites par un algorithme (ou tout mécanisme de calcul).