calcolabilita

calcolabilita

calcolabilità in logica, termine che indica la possibilità di descrivere in modo sequenziale, deterministico e finito, una procedura di calcolo che consenta di pervenire a un dato risultato. Si parla quindi di funzione calcolabile (o funzione computabile) quando è possibile indicare un procedimento di calcolo, costituito da un numero finito di passi, che permetta di computare i valori che la funzione assume (→ algoritmo): ne è un esempio la funzione mcd(a, b) che calcola il massimo comun divisore fra i due numeri utilizzando l’algoritmo di Euclide. Analogamente, un insieme è detto decidibile quando è possibile stabilire, con un numero finito di operazioni, se un dato elemento appartiene o meno all’insieme stesso. Per esempio l’insieme dei numeri primi è decidibile nel senso che è possibile stabilire se un numero è primo o no provando a dividerlo per i numeri minori di esso. Il concetto di calcolabilità è quindi connesso all’esistenza di un algoritmo ed è alla base del funzionamento degli elaboratori elettronici: per accentuare questa caratteristica di eseguibilità della legge che la funzione esprime si parla di effettiva calcolabilità. La riflessione sul tema della calcolabilità, tuttavia, fu sviluppata da logici e matematici negli anni Trenta del Novecento, ben prima quindi della realizzazione dei calcolatori elettronici. In particolare il logico inglese A.M. Turing descrisse un automa esecutore in grado di eseguire azioni elementari e di comporle in modo tale da determinare i valori assunti da qualsiasi funzione calcolabile. Questo automa, detto macchina (universale) di Turing, è un automa teorico, consiste cioè in una descrizione concettuale che mostra come scomporre un processo di calcolo in singoli passi elementari (→ Turing, macchina di). La macchina di Turing è quindi un modello che fornisce una traduzione formale del concetto intuitivo di funzione calcolabile; allo stesso scopo sono stati introdotti altri modelli di calcolabilità fra i quali le → funzioni ricorsive generali e il λ-calcolo (→ lambda-calcolo). Questi modelli di calcolabilità sono equivalenti fra loro in quanto individuano una stessa classe di funzioni; ciò supporta la tesi di Church secondo cui le funzioni (intuitivamente) calcolabili coincidono con le funzioni ricorsive generali (→ Church, tesi di).

In termini più specifici: per funzione calcolabile s’intende una funzione aritmetica f che ha come dominio e codominio l’insieme dei numeri naturali (ƒ: N → N), per la quale sia definito un algoritmo che calcoli i valori della funzione stessa. Si distinguono funzioni calcolabili totali e funzioni calcolabili parziali:

• una funzione calcolabile si dice totale se è definita per ogni numero naturale, cioè se l’algoritmo che la calcola produce in output un risultato in un numero finito di passi, in corrispondenza di ogni numero naturale che gli viene assegnato in input;

• una funzione calcolabile si dice parziale se è definita solo per alcuni numeri naturali, cioè se l’algoritmo che la calcola termina solo per alcuni numeri naturali che gli vengono assegnati in input, mentre può non essere ben definito o non avere termine per gli altri numeri.

L’insieme delle funzioni calcolabili è un insieme numerabile. Tuttavia l’insieme delle funzioni aritmetiche ha una cardinalità maggiore del numerabile: da ciò si deduce che esistono funzioni aritmetiche che non sono calcolabili. Per costruire un esempio di funzione non calcolabile si considera la successione infinita numerabile di tutte le funzioni calcolabili totali, indicata con φ₁, φ₂, φ₃, ..., e si definisce per ognuna di esse la funzione ƒ(x) = φ(x) + 1. Con un ragionamento analogo al procedimento diagonale di → Cantor, si può dimostrare che tale funzione non è una funzione calcolabile totale.