funzione calcolabile

funzione calcolabile

funzione calcolabile funzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di ciascun valore ammesso per le sue variabili indipendenti. In generale, una funzione a una variabile associa a ogni valore del suo insieme di definizione uno e un solo valore di un insieme detto codominio. Se la funzione è calcolabile, tale corrispondenza è effettuata tramite un algoritmo di calcolo; per questo motivo una funzione calcolabile può essere pensata come un → automa in grado di elaborare l’informazione in ingresso e fornire, in modo univoco, il risultato in uscita. Un esempio elementare di funzione calcolabile è la funzione successore che associa a ogni numero naturale n il numero n + 1, suo successivo nell’ordinamento naturale. La funzione successore è indicata con il simbolo s e si ha, quindi: s(n) = n + 1. Le funzioni calcolabili possono avere anche più variabili: per esempio la funzione somma e la funzione prodotto, che rispettivamente associano a due numeri x e y il numero x + y e il numero x ⋅ y, sono funzioni calcolabili di due variabili. La loro effettiva calcolabilità è garantita, in entrambi i casi, dalla possibilità di definire una procedura deterministica e finita che, dati due numeri, permette di giungere al risultato, calcolare cioè la somma e il prodotto. Utilizzando funzioni calcolabili elementari, è possibile costruire funzioni più complesse, anch’esse calcolabili. Per esempio, indicando con A la funzione somma e con P la funzione prodotto si può costruire la funzione calcolabile A(P(x, s(y)), z), che si può interpretare come ƒ(x, y, z) = x ⋅ (y + 1) + z.

Non tutte le funzioni definibili sono calcolabili; c’è infatti una differenza sostanziale fra definire in modo coerente e matematicamente corretto una funzione e poterne calcolare il valore. Per esempio, l’algoritmo per il calcolo della divisione fra numeri interi può non avere termine, come nel caso della divisione fra 5 e 3 (5 : 3 = 1,6666...): la funzione che associa a ogni coppia di numeri interi positivi x e y il loro rapporto x : y non è quindi una funzione calcolabile, bensì semicalcolabile, perché la procedura di calcolo che la definisce è finita in alcuni casi e non lo è in altri. Nel caso della divisione è comunque possibile modificare l’algoritmo in maniera tale da renderlo finito, imponendo che si fermi a una data cifra decimale. Esistono tuttavia casi in cui la funzione è intrinsecamente non calcolabile. Per esempio, tra i 23 problemi posti da Hilbert (→ Hilbert, problemi di), il decimo chiede di definire un algoritmo per stabilire se una qualunque equazione diofantea (equazione cioè a coefficienti interi), abbia o meno soluzioni intere. In modo equivalente il problema si può così formulare: definire per casi una funzione ƒ sull’insieme dei polinomi a coefficienti interi tale che per ogni polinomio p

Questa funzione, pur essendo ben definita da un punto di vista matematico, nel senso della possibilità di impiegare il principio del terzo escluso per definire oggetti, non è calcolabile: nel 1970, il matematico russo J. Matijasevič ha, infatti, dimostrato che il problema è indecidibile (→ decidibilità). L’esistenza di funzioni non calcolabili, come quella appena descritta, determina l’esigenza di capire quante e quali siano le funzioni calcolabili all’interno delle funzioni ben definite. Innanzitutto, poiché il concetto di funzione calcolabile discende dal concetto di algoritmo e poiché in un automa esecutore i dati e i risultati sono rappresentati in modo discreto, il dominio di una funzione calcolabile è anch’esso discreto. Ciò comporta che una funzione calcolabile ha come dominio e come codominio l’insieme dei numeri naturali; è, quindi, una funzione aritmetica. L’insieme delle funzioni calcolabili è un sottoinsieme dell’insieme delle funzioni aritmetiche; tuttavia esistono funzioni aritmetiche che non sono calcolabili. Inoltre, mentre le funzioni calcolabili costituiscono una infinità numerabile, l’insieme delle funzioni aritmetiche non calcolabili ha cardinalità superiore al numerabile (→ funzione caratteristica). Si può quindi affermare che gli oggetti matematici che si possono effettivamente costruire sono soltanto una piccola parte di quelli che si possono coerentemente definire.

Allo scopo di fornire una traduzione rigorosa del concetto di funzione calcolabile, a partire dagli anni Trenta del Novecento sono stati introdotti e studiati alcuni modelli formali per descrivere il processo di calcolo di una funzione. Fra i modelli di calcolo introdotti ci sono le → funzioni ricorsive, la macchina di → Turing e il λ-calcolo (→ lambda-calcolo). Secondo la cosiddetta tesi di → Church, l’insieme delle funzioni ricorsive rappresenta in maniera adeguata l’insieme delle funzioni calcolabili nel senso che ogni funzione calcolabile può essere definita come funzione ricorsiva e, viceversa, ogni funzione ricorsiva è una funzione calcolabile. La tesi di Church è avvalorata dal fatto che tutti i formalismi finora introdotti per descrivere le funzioni calcolabili sono equivalenti fra loro, rappresentano cioè la stessa classe di funzioni.