In matematica le funzioni elaborano dei numeri e producono dei risultati.
Una funzione si dice calcolabile se rispetta una delle seguenti condizioni:
1) sono in grado di calcolarla
2) posso inventare un metodo per calcolarla
Ad esempio non è calcolabile la funzione che elenca tutti i numeri decimali compresi in un intervallo, perché l’algoritmo non termina in un numero finito di passi.
Può sembrare banale, ma il teorema matematico della calcolabilità si riassume all’incirca con le due condizioni indicate sopra. Si appoggia sul concetto di "intuitivamente" calcolabile e di algoritmo (cioè processo di calcolo o insieme di passaggi) per giungere al risultato.
I matematici Church e Turing enunciarono una tesi indimostrabile per cui le funzioni calcolabili sono quelle per cui posso inventare un algoritmo risolvibile da una macchina di Turing, sostanzialmente un computer.
Ci sono molte classi di funzioni non calcolabili, l’esempio classico sono le enumerazioni. Una funzione che elenca tutti i numeri interi non è calcolabile. Una funzione che elenca tutte le combinazioni delle lettere dell’alfabeto, con numero arbitrario di posizioni, non è calcolabile.
Un altro esempio classico è una funzione che stabilisca se una equazione a coefficienti interi di grado arbitrario ammette soluzione intere, detto decimo problema di Hilbert e relativo teorema di Matijasevič che ne dimostra la non calcolabilità.