Un problema si dice computabile se la sua soluzione può essere descritta mediante un algoritmo.
I problemi che non sono risolvibili con un procedimento algoritmico si dicono non computabili.
Per poter affermare che un problema è non computabile, e quindi insolubile, bisogna “dimostrare” che non esiste una soluzione algoritmica.
Ci sono dei problemi per cui non si riesce a trovare una soluzione algoritmica, ma non si riesce nemmeno a dimostrare che non esiste una soluzione.
I problemi si possono quindi dividere in:
-
problemi computabili se esiste una soluzione algoritmica;
-
problemi non computabili se è dimostrato che non esiste una soluzione algoritmica;
-
problemi che per il momento vengono considerati non computabili ma per cui potrebbe essere trovata prima o poi una soluzione.
