Dominio, terminazione e garanzie di un procedimento
Un procedimento supera tutte le prove eseguite su numeri pari. Riceve poi un numero dispari e continua a lavorare senza fermarsi. Per giudicarlo dobbiamo conoscere una condizione preliminare: doveva accettare soltanto numeri pari, oppure qualunque intero non negativo? Lo stesso comportamento può rispettare il primo impegno e violare il secondo.
Formalizzare la nozione di algoritmo significa rendere espliciti questi impegni: quali ingressi ammettere, quali operazioni eseguire e quale risultato garantire. Finitezza, chiarezza, eseguibilità, correttezza ed efficienza descrivono proprietà distinte, ciascuna con precise condizioni di validità.
Un procedimento e il suo campo di validità
Consideriamo un compito elementare: dato un numero pari e non negativo di oggetti, calcolare quante coppie si possono formare. Gli oggetti non devono essere descritti individualmente: l'ingresso è soltanto il loro numero n.
Una procedura possibile conserva una quantità residua r, inizialmente uguale a n, e un conteggio c, inizialmente nullo. Finché r è diverso da zero, sottrae due da r e aggiunge uno a c. Quando r raggiunge zero, restituisce c.
Per n = 8, il residuo attraversa i valori 8, 6, 4, 2, 0 e il risultato è 4. Per n = 7, invece, attraversa 7, 5, 3, 1, −1, −3 e continua: la sottrazione di due conserva la disparità, quindi zero non verrà raggiunto. Questo secondo comportamento è descritto nel modello degli interi matematici esatti; una macchina con interi di dimensione fissa può introdurre overflow e un comportamento ulteriore.
Il dominio ammesso della prima richiesta è dunque:
D = {0, 2, 4, 6, …}.
La procedura termina per ogni elemento di D. Il caso n = 7 non confuta questa garanzia, perché non appartiene a D. Se vogliamo ammetterlo, dobbiamo estendere la richiesta: decidere come trattare l'oggetto spaiato, oppure prevedere un rifiuto esplicito. Limitarsi a chiamarlo «caso particolare» lascia incompleta la specifica.
Questo è il ruolo del dominio: fissare gli ingressi sui quali assumiamo un obbligo. La correttezza di una soluzione viene valutata rispetto agli ingressi e alle uscite ammessi dal problema.
La finitezza contiene due affermazioni diverse
La descrizione del procedimento occupa poche righe. Questa è la finitezza della descrizione: un insieme limitato di regole può governare ingressi di dimensioni arbitrariamente grandi. La finitezza dell'esecuzione richiede invece che ogni ingresso ammesso conduca all'arresto.
Per la procedura delle coppie, su n appartenente a D, il numero di ripetizioni è esattamente n/2. È finito per ogni ingresso, ma cresce senza un limite unico al crescere di n. La garanzia ha la forma:
per ogni n in D esiste un tempo finito T(n) entro cui il calcolo termina.
Non afferma che esista uno stesso tempo massimo valido per tutti i numeri pari. L'ordine delle espressioni «per ogni» ed «esiste» cambia il contenuto dell'impegno.
Inoltre, la condizione «fermati quando r = 0» specifica quando uscire, ma non dimostra che si uscirà. Il confronto fra 8 e 7 lo rende concreto: la stessa condizione è raggiungibile nel primo caso e irraggiungibile nel secondo. Nelle prove algoritmiche, la terminazione richiede perciò una giustificazione distinta dalla validità del risultato all'uscita.
Chiarezza ed eseguibilità non garantiscono l'arresto
La regola «sottrai due» è precisa anche quando il residuo diventa negativo. Ogni sottrazione è eseguibile sugli interi esatti. Eppure, partendo da 7, la procedura non termina. Abbiamo così separato tre proprietà spesso presentate insieme: significato delle istruzioni, possibilità di eseguirle e arresto dell'intero processo.
L'eseguibilità va riferita a un modello. Se un passo ordina di consultare una tabella infinita già compilata per ogni possibile ingresso, non abbiamo fornito una realizzazione effettiva ordinaria della procedura. Occorre spiegare come ottenere l'informazione richiesta mediante operazioni disponibili. Il requisito non viene soddisfatto dalla sola precisione grammaticale della frase. L’eseguibilità richiede che i passi siano effettivamente computabili nel modello adottato.
Anche il rapporto tra chiarezza e determinismo richiede una distinzione. Una scelta casuale può essere definita precisando insieme dei risultati possibili e distribuzione. Gli esiti variano, mentre la regola resta non ambigua. La nozione generale comprende quindi algoritmi randomizzati; per essi vanno esplicitate anche le garanzie probabilistiche di risultato e terminazione.
Correttezza: una relazione da rispettare
Nel compito delle coppie, l'uscita corretta è un intero non negativo c tale che:
2c = n.
Questa relazione specifica ciò che il risultato deve soddisfare, senza imporre di produrlo attraverso sottrazioni successive. Possiamo indicare con Q(n, c) l'affermazione «c è intero non negativo e 2c = n». La garanzia completa richiesta alla procedura A è allora:
per ogni n in D, A termina e restituisce un c per cui Q(n, c) è vera.
La correttezza parziale richiede che Q sia vera quando il procedimento termina. La correttezza totale comprende anche la terminazione su tutti gli ingressi ammessi. Nella procedura considerata, dopo k ripetizioni il residuo è n − 2k e il conteggio è k; per n pari e non negativo, a k = n/2 l'arresto avviene con il risultato richiesto.
Se a ogni sottrazione aggiungessimo due al conteggio, l’arresto resterebbe garantito su D, ma da n = 8 otterremmo c = 8, violando 2c = n. Aumentare la velocità non correggerebbe questo difetto. Analogamente, stampare «errore» per ogni ingresso non risolverebbe il compito: un messaggio di errore è un'uscita accettabile soltanto nei casi in cui la specifica lo consente.
La funzione calcolata non identifica il procedimento
Sul dominio D, la procedura delle sottrazioni calcola la funzione f(n) = n/2. Possiamo ottenere lo stesso valore anche mediante una divisione intera per due, realizzata con un metodo appropriato alla rappresentazione dei numeri.
Le due strategie coincidono sul risultato richiesto, ma organizzano diversamente il lavoro. Sapere che entrambe calcolano f non basta a stabilire quanto tempo e quanta memoria richiedano. La funzione descrive la corrispondenza fra ingressi e risultati; la descrizione algoritmica stabilisce il modo di ottenerli.
Questa distinzione permette di confrontare algoritmi diversi per lo stesso compito senza cambiare il significato di «corretto». La specifica resta il riferimento comune; i procedimenti diventano oggetti separati di analisi.
Efficienza: quanto è lungo l'ingresso?
Per le sottrazioni successive abbiamo contato n/2 iterazioni. Ma n è il valore dell'ingresso, non necessariamente la lunghezza della sua rappresentazione. Un intero positivo scritto in binario occupa b = ⌊log₂ n⌋ + 1 bit.
Prendiamo n = 2ᵇ − 2, con b almeno uguale a 2. Questo numero è pari, richiede b bit e provoca 2ᵇ⁻¹ − 1 iterazioni. Un conteggio lineare nel valore n diventa dunque esponenziale nella lunghezza b. Sono risultati aritmetici sul procedimento descritto, non tempi misurati su un computer.
Il conteggio delle iterazioni non esaurisce il costo: sottrarre, aggiornare il contatore e verificare l'arresto hanno a loro volta un costo dipendente dalla rappresentazione. È proprio per evitare confronti equivoci che un'analisi deve dichiarare dimensione dell'ingresso e operazioni considerate elementari.
La procedura delle sottrazioni rimane corretta e terminante su D anche quando richiede troppe operazioni per un impiego pratico. L'efficienza è quindi una proprietà da valutare dopo aver fissato problema e modello; non una condizione che, da sola, definisce l'appartenenza alla categoria di algoritmo.
La definizione che possiamo ora usare
Per il calcolo deterministico terminante, chiamiamo algoritmo un procedimento con descrizione finita e regole non ambigue, composto da operazioni effettive, che conclude l'esecuzione su ogni ingresso del dominio dichiarato. Dire che risolve un problema aggiunge la correttezza rispetto alla specifica. Dire che è efficiente richiede una valutazione delle risorse e della dimensione degli ingressi.
Il criterio acquisito qui è già operativo: ogni affermazione su un algoritmo deve rendere riconoscibili il dominio in cui vale, la garanzia che offre e le condizioni sotto cui è stata stabilita.