Informazione tecnologica

Problemi facili, difficili, impossibili…

Il 25 marzo, alle ore 17.00, la Prof. Simona Ronchi della Rocca (Università di Torino) terrà l'ottava  conferenza de I Mercoledì dell'Accademia 2020.

Abstract

Siamo sempre più abituati a delegare al calcolatore l’organizzazione della nostra vita, dalla gestione del conto corrente alla prenotazione dei biglietti del treno, e questo ha pericolosamente diffuso l’idea che questa macchina sia in qualche modo “onnipotente”, cioè possa rivolvere magicamente ogni nostro problema. Ma cosa significa risolvere un problema in modo automatico, cioè tramite un calcolatore? Dobbiamo innanzitutto restringere la classe dei problemi, e considerare solamente quelli che possano essere automatizzati, cioè la cui soluzione consiste in un algoritmo eseguibile da una macchina. Algoritmo: una parola che viene oggi abusata, ma che indica semplicemente una sequenza finita, non ambigua, di azioni automatizzabili. Problemi etici, esistenziali, filosofici (tipo l’esistenza di Dio) non fanno ovviamente parte di questa classe. Restringendo in questo modo il nostro campo di indagine, possiamo chiederci se tutti i problemi possono essere risolti. La risposta è negativa, poichè esistono problemi di questo tipo, pure ben posti, che non possono essere risolti. La loro non risolubilità è assoluta, non dipende dalla potenza del calcolatore che usiamo. Il primo di tali problemi è stato trovato da Alonzo Church e Alan Turing nel 1936, ma il loro numero è infinito, e purtroppo tra questi ci sono problemi la cui soluzione sarebbe utilissima. Se ci restringiamo ai problemi per i quali esiste una soluzione, possiamo chiederci se è possibile in qualche modo misurarli, cioè determinare se alcuni sono più difficili di altri. La nozione di difficoltà non è facile da definire: l’algoritmo che risolve il problema è trovato da un essere umano, il calcolatore si limita ad eseguirlo. E trovare l’algoritmo dipende dalla bravura della persona, dalla sua cultura, dalla sua fantasia e a volte dalla sua fortuna: tutte qualità non misurabili. Ma siamo in una economia di mercato, e in quest’ottica misuriamo i problemi secondo il costo della loro soluzione, costo che può essere espresso in termini di risorse (tempo, spazio, energia) di cui il calcolatore ha bisogno per eseguirla. Qui possiamo allora discriminare tra problemi detti “fattibili”, che hanno un costo accettabile, e “infattibili”, che sono sì risolubili ma richiedono risorse eccessive. Ad esempio, se vogliamo calcolare il valore esatto di 2 elevato a 100, indipendentemente dal tipo di calcolatore usato il tempo richiesto sarebbe dell’ordine del numero dei microsecondi trascorsi dal big-bang ad ora! I problemi infattibili sono quindi risolubili in teoria, ma non nella realtà. Tale classificazione, studiata dalla teoria della complessità, che è una delle teorie fondanti dell’informatica, non è però completa, nel senso che esistono problemi che non sappiamo catalogare come fattibili o infattibili, ma di cui conosciamo solo soluzioni troppo costose. Purtroppo molti dei problemi con cui abbiamo a che fare quotidianamente appartengono a questa categoria incerta (fare un orario scolastico, ad esempio). Come facciamo? una branca dell’intelligenza artificiale si occupa di risolvere problemi di questo tipo, limitando a priori il numero delle possibili soluzioni, cioè imponendo delle scelte arbitrarie. Il problema della completezza della catalogazione (denominato “P=PN?”) è considerato uno dei più importanti problemi aperti dell’informatica, al punto che un premio di un milione di dollari è stato messo in palio per chi riuscirà a risolverlo! Per ora la scienza prosegue per ipotesi; l’ipotesi negativa (questi problemi sono davvero infattibili) per ora è vincente, e molti algoritmi che regolano la nostra vita, ad esempio quelli che controllano la sicurezza delle comunicazioni, sono basati su di essa. Quindi non c’è la certezza che le nostre comunicazioni siano davvero sicure, sono “probabilmente” sicure, perchè dipendono da una ipotesi. Inoltre questa catalogazione non è assoluta: la computazione quantistica, per ora allo stadio embrionale, potrebbe in linea di principio mutarla, trasformando problemi infattibili in problemi fattibili. La conclusione è che l’informatica, come del resto tutte le scienze, non è il regno delle certezze, ma è un campo in continua evoluzione. Non fidiamoci troppo del calcolatore!  

 

Sala dei Mappamondi, ingresso da Via Accademia delle Scienze 6

Vai al programma completo del ciclo