Una funzione è calcolabile se esiste un programma che la calcola.
Esempio: esiste un programma che determina se domani piove o no, restituendo 0 o 1, anche se non sappiamo qual è.
- Ogni funzione booleana è calcolabile? → si (metodo di dimostrazione per intimidazione)
- No, perché l’insieme (infinito) delle funzioni booleane non è numerabile, perché ogni funzione booleana è la funzione caratteristica di un sottoinsieme di (vedi: insieme delle parti, invece l’insieme (infinito) dei programmi (di lunghezza finita) che si possono scrivere è numerabile.