La domanda con cui ci siamo lasciati nel post precedente era se sia sempre possibile trovare l’algoritmo per effettuare l’elaborazione che abbiamo in mente.
A questo scopo bisogna prima di tutto chiarire che le situazioni alle quali possiamo applicare gli algoritmi richiedono che sia possibile descrivere con precisione sia l’insieme dei possibili dati di ingresso (detto input) all’algoritmo stesso che l’insieme dei risultati in uscita (detto output) accettabili, espressi in funzione degli input. Ma anche per i problemi formulabili in questo modo, vedremo nel seguito che la risposta è negativa. Aggiungiamo che la descrizione viene eventualmente fatta, per algoritmi che non terminano mai perché le elaborazioni che devono effettuare non si devono interrompere, con riferimento a un determinato intervallo temporale.
Consideriamo adesso quattro problemi che presentano caratteristiche diverse in termini di computabilità (o calcolabilità, i nomi che denotano il settore dell’informatica che si occupa di questi aspetti), che verranno discusse in questo e nel successivo post.
- Un primo esempio di problema (detto “ordinamento”) affrontabile algoritmicamente prevede in input una lista di N numeri interi e richiede in output la lista dei numeri ordinati per valore crescente.
- Un secondo esempio di problema (detto “cammini minimi”) prevede in input una lista di N città, per ognuna delle quali è specificato un elenco di città (appartenenti alla lista stessa) alle quali esse sono connesse direttamente da un tratto di strada di cui viene data la lunghezza. In output si richiede, per ogni coppia di città P e Q dell’elenco, la successione dei tratti di strada che porta da P a Q che ha lunghezza totale minima.
- Un terzo esempio (detto “commesso viaggiatore”) ha lo stesso input del secondo, ma l’output richiede di ottenere una successione di tratti di strada che passi per tutte le città dell’elenco una volta sola e abbia lunghezza totale minima.
- Un quarto problema (detto “arresto”) ha come input uno specifico programma scritto in un determinato linguaggio di programmazione e uno qualunque dei possibili dati di ingresso al programma. L’output richiesto è “VERO” se quel programma elaborando questi dati si arresta dopo un tempo finito, “FALSO” altrimenti.
Osserviamo che l’algoritmo, per essere tale, deve “funzionare”, cioè produrre l’output corretto, per tutti i possibili input. Ciò vuol dire, per il primo problema, per tutte le possibili liste di N numeri; per il secondo e il terzo problema, per tutte le possibili liste di N città con tutte le possibili connessioni a città adiacenti; per il quarto problema, per tutti i possibili programmi scritti nel linguaggio scelto e tutti i loro possibili dati di ingresso.
Per i primi tre problemi sopra descritti esistono algoritmi risolutivi, quindi si dice che i problemi sono computabili, mentre il quarto problema, quello dell’arresto, non ammette alcun algoritmo risolutivo, ed è quindi un problema incomputabile. A questo punto qualcuno potrebbe pensare, visto che un algoritmo deve essere comunque espresso in un determinato linguaggio di programmazione mediante un programma che deve essere eseguito da un determinato automa, che basterebbe avere un linguaggio più moderno o un automa più potente.
Non è così. È stato proprio Alan Turing a dimostrare, nell’articolo scientifico del 1936 che viene considerato la nascita dell’informatica come disciplina scientifica autonoma, che il quarto problema non è intrinsecamente risolvibile, a prescindere da quale siano il linguaggio di programmazione o l’automa usati. In altre parole, non esiste un algoritmo per il problema dell’arresto.
Sottolineo che tale risultato rimane vero anche considerando automi di tipo “quantistico” (che sono il modello teorico dei cosiddetti “computer quantistici” di cui molto si parla in questi anni). Si tratta di un risultato importantissimo, non solo dal punto di vista culturale ma anche su un piano filosofico, perché definisce dei limiti ben precisi a ciò che può essere realizzato mediante i calcolatori e, quindi, anche alla nostra possibilità di “conoscere” qualcosa attraverso procedimenti algoritmici. Il che non può che farci piacere, visto che come esseri umani abbiamo a nostra disposizione altri modi di “conoscere”, che esulano dall’assoluta razionalità meccanica di un automa e che questi ultimi non possiedono.
Nel prossimo post ci occuperemo del tempo necessario per l’esecuzione degli algoritmi e di come questo possa variare da situazioni accettabili ad altre del tutto insostenibili.
( I post di questa serie sono basati sul libro dell’Autore La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, al quale si rimanda per approfondimenti. I lettori interessati al tema possono anche dialogare con l’Autore, su questo blog interdisciplinare. )