teoria della calcolabilità

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, che a livello pratico potrebbero essere proibitive. Questa disciplina è comune sia alla matematica sia all'informatica. Di conseguenza l'obiettivo principale è dare una definizione formale e matematicamente rigorosa dell'idea intuitiva di funzione calcolabile. Da una parte l'approccio è quello di approfondire il concetto di calcolabilità, cercando di individuare le categorie di problemi che sono teoricamente risolvibili, e dall'altra mappare questo concetto su ciò che è teoricamente calcolabile sui computer, sempre senza considerare le limitazioni imposte dai costi, dal tempo e dalla quantità di memoria impiegata. Un altro importante aspetto è quello di definire matematicamente il concetto di algoritmo in modo che i programmi possano essere concretamente pensati in termini di oggetti matematici, più precisamente come funzioni che restituiscono un determinato risultato a partire da un certo insieme di dati in ingresso.