La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico. In altre parole, essa cerca di determinare se una data funzione è teoricamente calcolabile, a prescindere dal fatto che sia anche trattabile (cioè a prescindere dalla quantità di risorse che la sua esecuzione richiede in termini di tempo o di memoria, e che a livello pratico potrebbero essere proibitive). Questa disciplina è comune sia alla matematica che all'informatica''.