Iniziamo col dire che il concetto di infinito non è affatto amichevole nella branca della matematica che ci riguarda più da vicino, ovvero l'informatica teorica. Tale concetto, per noi, si presenta sempre a braccetto con quello di impossibile, ovvero non computabile, che è l'espressione più sgradita in assoluto per qualsiasi informatico, in relazione ad un particolare problema.
E' facile rendersi conto di quanto sopra considerando l'oggetto centrale di tutti gli sforzi di teorici, analisti e programmatori, ovvero la definizione fondamentale di algoritmo:
|
Si definisce algoritmo una sequenza finita di passi eseguiti secondo un numero finito di regole e di operazioni esplicite, che da un insieme di dati in entrata X produce un insieme di dati in uscita Y (in termini funzionali, si tratta di una applicazione che va da X in Y). |
Questa funzione, per
essere utile, deve essere computabile: deve esistere un metodo tramite il quale sia possibile descriverne tutti i singoli valori. Appare
dunque chiaro che la computazione non può richiedere un
numero di passi infinito (in tal caso si avrebbe un algoritmo che
non termina mai), e neppure, considerazione forse più
sottile, può richiedere un numero infinito di regole e/o di
operazioni per il suo svolgimento. Seguendo l'intuizione fornita
da quest'ultima affermazione, Böhm e Jacopini hanno dimostrato
un importantissimo teorema, secondo il quale qualsiasi algoritmo può
essere implementato tramite un linguaggio semplificato che supporti
solamente sequenze e cicli con precondizione di tipo "While"
(Teorema di Böhm-Jacopini sull'espressività dei
linguaggi di programmazione).
Ecco quindi che risorse significativamente importanti dell'informatica teorica sono dedicate alla trasformazione di successioni e procedure di calcolo infinite in serie finite di steps discreti, che possano fornire risultati parziali e/o approssimazioni. Esempi divertenti e facilmente fruibili, in questo senso, sono gli algoritmi per il calcolo del'n-esima cifra di pigreco, per l'i-esimo termine di successioni come quella di Fibonacci senza approssimazione, o anche il semplice algoritmo non ricorsivo per il calcolo del fattoriale di numeri giganti... quest'ultimo banale esempio ci conduce ad una ulteriore considerazione: problemi apparentemente banali e notoriamente nel dominio del finito possono produrre, in modo pressochè inaspettato per i profani, tempi di computazione non infiniti, ma pericolosamente superiori all'aspettativa di vita media di un essere umano (o dell'intero sistema solare, a volte...).
Naturalmente, se
l'infinito è messo alla porta, i suoi parenti più
stretti - gli infinitesimi - sono sicuramente in grado di rientrare
dalla simbolica finestra (ogni riferimento a sistemi operativi
esistenti e prodotti a Redmond è assolutamente casuale :-)):
l'optimum algoritmico, infatti, sarebbe l'esecuzione in tempi
nulli, o realisticamente tendenti a zero. Anche qui, però,
i tempi (finiti) di esecuzione delle singole istruzioni sugli
elaboratori fisici costituiscono un limite teoricamente invalicabile
verso la più spinta compressione dei tempi di elaborazione.
Esistono tuttavia anche ulteriori vincoli, di natura teorica, che
limitano ulteriormente la possibilità di trovare l'algoritmo
in assoluto più veloce per un dato problema, o per una intera
categoria di problemi.
Cionondimeno, la ricerca dell'algoritmo
più veloce in assoluto, o quantomeno della relativa
efficienza all'interno di un pool di soluzioni finito e ben
noto, per un determinato problema, rimane uno dei compiti
fondamentali, nonché più ardui, dell'informatica, e
costituisce il nucleo primitivo della scienza
dell'ottimizzazione.
Si parte dalla
intuitiva considerazione che, di norma, un algoritmo
deve poter elaborare i
propri dati fornendo i risultati in tempi ragionevoli: un
algoritmo che impiegasse un
miliardo di anni per calcolare l'ammontare della vostra pensione
sociale non sarebbe affatto efficiente, se si esclude l'ovvio
vantaggio apportato alle casse dell'INAIL :-).
A livello
teoretico, non siamo però interessati a dover scrivere un
algoritmo specifico per ogni problema (come invece avviene nella
pratica operativa e nell'approccio classico): è molto più
interessante e produttivo operare ad un metalivello, che ci consenta
di trattare ampie classi di problemi, da cui eventualmente derivare
forme algoritmiche ad hoc. Orbene, è dimostrato (da Blum, nel
noto teorema dello Speed-up) che esistono moltissimi problemi per i quali non esiste
l'algoritmo più veloce.
Consolatevi:
per problemi del genere esiste sempre una sequenza non computabile di
algoritmi impossibili, di dimensioni e di complessità
crescenti.
In ogni caso, è ben noto in informatica
che una vasta classe di problemi
può essere descritta in termini di specifiche formali (un
ampio ed interessante territorio, che prevede anche specifici
linguaggi come Z, Scheme, MZ, RZ) nel modo seguente:
|
Data la specifica formale f (logica, matematica, simbolica in genere, ma non necessariamente algoritmica) di un problema dipendente da più parametri in X, si cerca l'algoritmo più veloce che ne calcoli la soluzione in Y, cioè si vuole costruire l'algoritmo che calcoli la funzione f: X --> Y. |
L'approccio teoretico
più moderno tende a considerare solamente algoritmi
che risolvono un dato problema con tempo limite basso (constrained
algorithms), il che costituisce già un problema di
ottimizzazione, ovviamente traslato al metalivello computazionale di
generazione degli algoritmi stessi.
Prendendo in considerazione
solo algoritmi rapidamente computabili,
e lavorando in classe
asintotica, M.
Hutter è riuscito a proporre l'algoritmo
asintotico più veloce per risolvere ogni problema f ben
definito. Il che sposta i termini del problema sulla corretta
definizione della specifica f,
ovviamente, anche se questo rappresenta un problema più
trattabile, e soprattutto non modifica gli attributi dei problemi
NP-ardui ed NP-completi ben noti, rappresentando tuttavia un ottimo
progresso in campo teorico (ed ovviamente applicativo) nella teoria
della computabilità.
Volendo chiudere con una (facile) battuta, si
potrebbe dire che un passo infinitesimale è stato compiuto per
allontanarsi dallo spettro della computazione infinita...
Fine intervento