I programmi di computer si somigliano tutti: prendono un input e restituiscono un risultato. Ciascun programma deterministico calcola il risultato a modo suo, ma allo stesso input associa sempre lo stesso risultato. I programmi non-deterministici sono sottosopra: dato lo stesso input, esecuzioni diverse dello stesso programma possono restituire risultati diversi.
Una calcolatrice, solitamente, implementa un programma deterministico: se si digita 3+2 il risultato sarà sempre 5. Pensate ora, invece, a una calcolatrice che decide, di volta in volta e al posto vostro, che operazione eseguire sui numeri che digitate sulla tastiera. Mercoledì pomeriggio, premete 3, 2 e poi invio, e la calcolatrice restituisce il risultato 5. Premete 3, 2 e poi invio giovedì mattina, e la stessa calcolatrice restituisce il risultato 6. E la calcolatrice non è rotta, semplicemente ha eseguito la somma di 3 e 2 mercoledì pomeriggio, mentre giovedì mattina ha eseguito il prodotto di 2 e 3. Ecco, questa calcolatrice implementa un programma non-deterministico: dato lo stesso input (la coppia di numeri 3 e 2), seleziona in modo casuale quale operazione eseguire con questo. Un esempio sciocco, forse, ma piuttosto chiaro. Bene, questa calcolatrice probabilmente non è molto utile, ma, in certi casi, un programma in grado di eseguire operazioni diverse selezionando quale eseguire di volta in volta e in maniera casuale può essere estremamente utile.
Uno degli esempi classici più semplici è l’algoritmo quicksort per ordinare liste di numeri. L’algoritmo funziona all’incirca come segue. L’input è una lista di numeri disordinata, come, ad esempio:
«3,7,12,2,3,1».
Il risultato sarà una lista contenente gli stessi numeri ma ordinati dal più piccolo al più grande. Ovvero, in questo caso, «1,2,3,3,7,12». Per fare questo, l’algoritmo spezza la lista in due liste più corte, una contenente i numeri piccoli e una i numeri grandi della precedente lista. Supponiamo, per il momento, che un numero sia piccolo se minore di 7 e che, altrimenti, sia grande. Di questa scelta, al momento immotivata, riparleremo più avanti. Spezzando in due la lista precedente, otteniamo
«3,2,3,1» e «7,12».
Notate che i numeri non vengono ancora riordinati, ma solo inclusi uno ad uno in una delle due liste nello stesso ordine in cui erano prima. Le liste ottenute vengono spezzate nuovamente in numeri piccoli e numeri grandi scegliendo di nuovo una definizione di piccolo e di grande: «3,2,3,1» viene spezzata, ad esempio, in «2,1» e «3,3», se consideriamo piccolo ogni numero minore di 3; e «7,12» in «7» e «12», se consideriamo piccolo ogni numero minore di 12. Quindi, ora abbiamo
«2,1», «3,3», «7» e «12».
Se spezziamo anche le ultime due liste rimaste che abbiano più di un elemento, otterremo le seguenti sei liste da un elemento ciascuna:
«1», «2», «3», «3», «7» e «12»
che, se concatenate nell’ordine in cui sono, ci danno la lista desiderata:
«1,2,3,3,7,12».
Ora, il segreto per riordinare velocemente una lista con quicksort consiste nello scegliere bene la definizione di numero piccolo e numero grande ogniqualvolta si deve spezzare una lista in due. La prima volta che l’abbiamo fatto abbiamo scelto di dividere numeri grandi e numeri piccoli rispetto al numero 7. In generale, vorremmo che questa divisione facesse sì che, ogni volta che spezziamo una lista, la spezziamo in due liste di lunghezza simile: circa la metà della lunghezza della lista che stiamo spezzando. Per scegliere un numero che faccia con certezza una divisione di questo genere, bisogna aver già riordinato tutta la lista. Ma questo non ci aiuta perché, se abbiamo già riordinato la lista, quicksort non ci serve a nulla. Entra in scena il non-determinismo: per scegliere in modo efficiente un numero che separi i numeri grandi dai numeri piccoli, si può scegliere un numero a caso dalla lista. Senza sapere nulla sull’ordine della lista, una scelta random ci dà ottime possibilità di spezzare spesso le liste in modo efficace.
È importante notare che quicksort non è nel complesso, per così dire, un algoritmo non-deterministico. Infatti, data la stessa lista in input, otterremo sempre la stessa linsta ordinata in output. Però all’interno di un programma che implementa l’algoritmo conviene usare un sotto-programma non-deterministico che sceglie casualmente un numero per separare i numeri piccoli dai numeri grandi. Esempi di programmi complessivamente non-deterministici si possono trovare, per esempio, nell’ambito dell’intelligenza artificiale. Nonostante molti programmi sviluppati mediante processi di apprendimento automatico (machine learning) siano deterministici, il comportamento di un programma durante l’apprendimento è squisitamente non-deterministico. L’apprendimento automatico consiste proprio in un processo di modifica graduale del modo in cui il programma risponde agli input che riceve. Questa modifica mira a far sì che gli output del programma si avvicinino progressivamente ad output ideali e, dunque, prevede che il programma, con il procedere dell’apprendimento, restituisca risultati diversi—migliori, auspicabilmente—a fronte degli input che riceve. Alcuni programmi, inoltre, vengono sviluppati con l’idea di mantenere attive le loro funzionalità di apprendimento anche durante il loro uso, e non solo in preparazione all’uso vero e proprio. Due esempi celebri sono gli assistenti virtuali Alexa a Siri. Questi sistemi sfruttano costantemente i dati relativi alle loro interazioni con l’utente al fine di dare risposte progressivamente più coerenti rispetto alle aspettative dell’utente stesso. Se si richiede la stessa cosa a questi sistemi in tempi diversi, dunque, può darsi che essi diano risposte diverse. Anche i sistemi per selezionare quali pubblicità debbano essere proposte agli utenti di certi social network sono in continuo stato di apprendimento. I parametri di scelta delle pubblicità vengono aggiornati ad ogni operazione dell’utente di modo che in futuro possano essere selezionate pubblicità maggiormente in linea con gli interessi dello stesso.
Un uso diverso di tecniche non-deterministiche di programmazione, invece, si trova in alcune funzioni del chatbot ChatGPT. Il modo in cui ChatGPT formula le sue risposte all’utente è fondato su un complesso processo di selezione della parola che ha maggior probabilità di seguire la serie di parole che compone la discussione avvenuta tra ChatGPT e l’utente. In altri termini, alla base di ChatGPT c’è un meccanismo estremamente complesso ed efficiente per scovare la parola più ovvia che possa essere pronunciata a seguito di quanto è stato detto. Questo meccanismo di base è probabilistico, ma deterministico. Ovvero, nonostante il meccanismo sia fondato su un calcolo della probabilità che certe parole possano occorrere in certi discorsi; dato lo stesso discorso di riferimento, il calcolo sarà sempre lo stesso, la probabilità calcolata sarà sempre la stessa e, dunque, la parola scelta da ChatGPT sarà sempre la stessa. Semplificando un po’, la probabilità di cui si parla qui non è la probabilità che ChatGPT dia una certa risposta ad una certa domanda, ma la probabilità che una certa risposta sia stata data in passato a quella domanda. Calcolata questa probabilità per le risposte possibili, ChatGPT sceglierà semplicemente e sempre la risposta più probabile. Quasi sempre, almeno. Infatti, la possibilità di alzare la temperatura di ChatGPT—temperature, in Inglese—fa sì che si possa impostare il programma in modo che la risposta restituita non sia sempre la più probabile, ma sia scelta in modo non-deterministico tra le più probabili. Questo dovrebbe corrispondere, si dice, ad introdurre un po’ di creatività in ChatGPT. Ora, se la capacità di creare cose nuove consista o meno nel fare la stessa cosa che si è sempre fatta, ma in due o tre modi lievemente diversi, per poi lanciare una moneta e scegliere a caso tra i risultati ottenuti, non sta a me dirlo. Resta il fatto che la versione creativa di ChatGPT è un ottimo esempio di programma non-deterministico.