Ci sono cose che le macchine non possono calcolare?

Se pensiamo ai computer in maniera sostanzialmente pre-teorica, tenendo conto, cioè, delle nostre intuizioni in merito senza sovrastrutture argomentative, difficilmente ci verrebbe da porci la domanda che apre questo paragrafo. Abituati come siamo alla natura pervasiva della tecnologia e alla crescente potenza di calcolo dei computer, verrebbe naturale pensare che a separarci da quelle operazioni ancora difficoltose sulle odierne macchine calcolatrici sia solamente una distanza temporale. Dopotutto, anche lo smartphone che portiamo in tasca è in grado di giocare una partita di scacchi in maniera più efficiente rispetto alla maggioranza di noi. Ben prima di smartphone, pocket PC e microchips, tuttavia, il problema che abbiamo tratteggiato in apertura ha meritato l’attenzione di matematici e studiosi brillanti, senza i quali il progresso tecnologico che possiamo apprezzare oggi sarebbe stato impensabile. La questione teorica che ha interessato questi studiosi, tra i quali ricordiamo sicuramente Alan Turing, riguarda la nozione di calcolo: cosa significa esattamente calcolare? E cosa è veramente calcolabile? Proprio per dare una definizione formalmente apprezzabile di algoritmo e di calcolo si dipanano inizialmente queste riflessioni. Sembra sensato, dunque, seguire il filo di questi pensieri, in modo tale da ricostruire i tasselli elementari che ci porteranno poi ad affrontare consapevolmente la domanda introduttiva posta poche righe fa.

Algoritmi e macchine di Turing

Ragioniamo ancora una volta a partire da nozioni pre-teoriche: quando pensiamo al concetto di algoritmo, quello che probabilmente ci sovviene è una sorta di procedimento sistematico, atto a risolvere un problema, a darci cioè una soluzione ad un quesito, in un numero finito (e ben determinato) di passaggi. Pensiamo, ad esempio, al famoso cubo di Rubik: a chi non è mai capitato, magari durante l’infanzia, di maneggiare questo famoso rompicapo dalle facce colorate? Ben presto, nel tentare di risolverlo, ci si rende conto che procedere a tentoni non è affatto la strategia migliore! Ecco che subentra il desiderio di una soluzione sistematica che riesca a portarci con sicurezza alla risoluzione in maniera meccanica, applicando cioè una procedura determinata e finita che non richieda un particolare sforzo concettuale: stiamo parlando nuovamente di un algoritmo! E ancora: quando ci viene insegnato a fare le addizioni nei primi anni di istruzione elementare non facciamo nient’altro che applicare un algoritmo mandato a memoria: applichiamo una procedura sistematica ad un problema, che questa volta consiste nel desiderio di sommare dei numeri. Conosciamo le regole del gioco, non ci resta che considerare l’input che ci viene dato – gli addendi – e applicare in maniera irriflessa tali regole. Non per nulla, con sufficiente pratica, diremo poi che fare addizioni ci viene automatico! Ancora in maniera intuitiva, dunque, possiamo riassumere la nozione di algoritmo tramite le parole di M. Frixioneⁱ:

Si dispone di un algoritmo (o di un metodo effettivo) per risolvere un problema se si dispone di un elenco finito di istruzioni tali che:

1) a partire dai dati iniziali, le istruzioni sono applicabili in maniera rigorosamente deterministica, in maniera cioè che ad ogni passo sia sempre possibile stabilire univocamente qual è l’istruzione che deve essere applicata al passo successivo;

2) si dispone di un criterio univoco per stabilire quando si è raggiunto uno stato finale, quando cioè il processo deve considerarsi terminato e il risultato, se esiste, è stato ottenuto;

3) uno stato finale deve sempre essere raggiungibile in un numero finito di passi.

Chiameremo input i dati di partenza del calcolo; output il suo risultato. Una funzione si dice calcolabile in modo algoritmico (o calcolabile in modo effettivo, o effettivamente calcolabile) se esiste un algoritmo che consente di calcolarne i valori per tutti gli argomenti.

Questa definizione, seppur soddisfacente ad un primo impatto, si rivelò pian piano insufficiente nel contesto degli studi sui fondamenti della matematica, intorno agli anni ‘30 del Novecento. Molti tra i più importanti logici del tempo tentarono, e riuscirono, nell’impresa di dare una definizione formalmente soddisfacente: tra questi, prenderemo in considerazione la soluzione di Alan Turing, che si configura come la più accessibile e intuitiva. Ciò che il logico inglese propone è infatti di analizzare il comportamento di un soggetto computante ideale: si chiede, in breve, in quali operazioni elementari possiamo riassumere l’operazione basilare del contare. Il risultato di questa analisi è la concettualizzazione di una macchina calcolatrice ideale, in grado di riprodurre nella maniera più semplice e completa possibile i passi compiuti da un qualsiasi agente che voglia seguire una procedura algoritmica. Partiamo di nuovo dalle nostre intuizioni: cerchiamo di definire nella maniera più elementare possibile questi passi. Che cosa facciamo, essenzialmente, quando eseguiamo un calcolo? Con le parole di M. D’Agostinoⁱⁱ:

Essenzialmente:

(i) leggiamo dei simboli (cifre o lettere dell’alfabeto) che sono contenuti in determinate “caselle” (i quadretti di un quaderno)

(ii) scriviamo dei simboli in determinate caselle;

(iii) cancelliamo qualche simbolo scritto in precedenza;

(iv) spostiamo il nostro sguardo da una casella all’altra;

(v) ci troviamo, ad ogni passo, in un certo “stato mentale” che indirizza le nostre azioni successive.

La Macchina di Turing (da qui in avanti, MT), lo ripetiamo, non è nient’altro che un costrutto concettuale che sintetizza questi cinque elementi in maniera leggermente più formale! Si compone, infatti, di un nastro potenzialmente infinito (immaginiamoci di disporre i quadretti di un foglio su di una unica riga, e di poter disporre di tutta la carta necessaria a compiere il nostro calcolo) e di una testina di lettura/scrittura (immaginiamoci che essa rappresenti noi stessi, impegnati nelle basilari operazioni del calcolo) in grado di leggere il simbolo presente nella casella del nastro su cui è posizionata (su cui si fissa la nostra attenzione, per continuare l’analogia), sovrascrivere il simbolo presente in questa casella (cancellarlo sovrascrivendolo con un simbolo vuoto o lasciarlo invariato sovrascrivendolo con se stesso), e spostarsi a destra o sinistra sul nastro (quello che i bambini fanno quando cambiano quadretto sul foglio, in sostanza). Gli unici due elementi supplementari di cui abbiamo bisogno sono: un alfabeto finito, contenente tutti i simboli che possiamo scrivere sul nastro, e una unità di controllo, contenente le istruzioni per eseguire il calcolo in oggetto (pensiamo, qui, per semplicità ad un programma per computer). In ogni momento del calcolo, la MT si trova in uno stato ben determinato, a cui corrispondono istruzioni precise di manipolazione dell’input (pensiamo, come anticipato da D’Agostino, al fatto che anche noi, quando calcoliamo, ci troviamo in un determinato “stato mentale” e che, in base ad esso, prendiamo decisioni su come manipolare i numeri che ci troviamo davanti). Quello che la MT fa, letto un dato simbolo e trovandosi in un dato stato, è rimpiazzarlo con un altro simbolo o con se stesso, spostarsi sul nastro, e cambiare (oppure rimanere nello stesso) “stato mentale” rispetto al passo precedente. In maniera leggermente più formaleⁱⁱⁱ:

In ogni dato stadio del calcolo la macchina si trova in un certo stato che appartiene a un certo insieme finito di stati possibili che comprendono uno stato iniziale (o stato 0) in cui la macchina si trova prima di cominciare. Ciascuna istruzione eseguita dalla macchina ha la forma seguente:

Se la macchina si trova nello stato S e legge il simbolo x, allora entra nello stato S0 , scrive il simbolo y al posto del simbolo x e si sposta di una casella a destra (oppure di una casella a sinistra).

Una tipica istruzione di una macchina di Turing viene rappresentata da una quintupla di questa forma:

(stato_attuale, simbolo_attuale, nuovo_stato, nuovo_simbolo, direzione)

La tesi di Turing

Arrivati a questo punto, siamo in grado, grazie al lavoro di Turing, di manipolare con maggiore chiarezza il concetto di algoritmo: MT, infatti, formalizza in maniera rigorosa la nozione di calcolo. Introduciamo ora quella che è passata alla storia come la tesi di Turing (spesso ribattezzata tesi di Church-Turing^iv). Secondo questa tesi, la nozione di Macchina di Turing cattura in modo esatto(!) il concetto intuitivo di algoritmo. Vediamo di specificare meglio la portata di questa affermazione. Secondo Turing (e in maniera semplificata rispetto alla formulazione originale^v):

Se un problema può essere risolto da una macchina (computer), allora può essere risolto da una macchina di Turing^vi.

È importante notare come la tesi di Turing sia di fatto una congettura: non può essere formalmente dimostrata, alla stregua di un teorema matematico, in quanto si configura come una proposizione universale, che potremmo eventualmente (e solamente!) falsificare. Più in dettaglio:

Tutti i problemi che possono essere risolti da un computer possono essere risolti da una macchina di Turing^vii.

Risulta chiaro che una affermazione del genere non può essere verificata (dovremmo farlo per ciascun computer, passato, presente e futuro, il che risulta impossibile). La congettura, di nuovo, può essere solamente falsificata. In altri termini: per farlo dovremmo mostrare, in futuro, un computer le cui operazioni non possono essere riprodotte da una MT. Fino ad oggi, la tesi di Turing (equivalente alla tesi formulata da Alonzo Church^{viii ix}) non è stata falsificata e molti scienziati la considerano alla stregua di un teorema logico-matematico. Aver introdotto questa posizione teorica si rivela di fondamentale importanza per la nostra domanda iniziale: ci sono cose che i computer non possono calcolare?

Problemi intrinsecamente non calcolabili: il problema della fermata

Come espresso in D’Agostino^x:

La tesi di Turing viene usata principalmente per mostrare che un problema non può essere risolto da un computer. A questo scopo è sufficiente mostrare che il problema non può essere risolto da una macchina di Turing. Il ragionamento assume la forma seguente (è un esempio di modus tollens):

1) Se il problema P può essere risolto da un computer, allora P può essere risolto da una MT

2) P non può essere risolto da una MT

C) P non può essere risolto da un computer

Risulta chiaro, ora, il procedimento secondo il quale è possibile argomentare a favore dell’insolubilità di un problema da parte di un computer. Nello schema presentato sopra il punto 1 rappresenta la tesi di Turing (di cui deve essere assunta la validità!), il punto 2 è il frutto di una dimostrazione logico-matematica (si considera il problema in oggetto e si ragiona su di esso e sul concetto di MT), da cui segue C, la conclusione. Capitale è la premessa 1: se non fosse assunta come vera, infatti, non potremmo giungere alla conclusione. Dato questo per assodato, vediamo ora uno dei più famosi esempi di problemi che intrinsecamente si configurano come non calcolabili (ovvero, non risolvibili mediante un algoritmo): il problema della fermata, o halting problem.

Il problema è riassumibile nel quesito seguente:

Dato un programma per computer P e un input I, P si ferma quando riceve I come input?^xi

Seguendo l’impianto argomentativo presentato poco sopra è possibile dimostrare (alla premessa 2) che non è possibile costruire una MT che possa rispondere a questo quesito. In altri termini (e se la tesi di Turing è vera): non possiamo costruire un computer(o una procedura algoritmica) che, presi in input una serie di istruzioni e l’input per questa serie, sappia dirci se tale set di istruzioni, con quel dato input, ci fornirà una soluzione (senza andare in loop). Turing stesso, in On Computable Numbers, with an Application to the Entscheidungsproblem, dimostrò che non può esistere una MT in grado di risolvere questo problema^xii. Anche ad un livello prettamente intuitivo, riusciamo a comprendere la portata enorme di questa dimostrazione in negativo: non possiamo determinare con certezza, quantomeno con un procedimento algoritmico, se un dato calcolo eseguito da una macchina terminerà mai; se ci darà, cioè, un output o se proseguirà in circolo all’infinito^xiii. Un impedimento davvero non indifferente!

Problemi troppo complessi: la complessità computazionale

Prima di concludere questa sommaria trattazione su ciò che i computer non possono calcolare, sembra opportuno spendere qualche parola per i problemi intrattabili: i problemi, cioè, che sono in linea teorica risolvibili da un calcolatore, ma non lo sono in pratica (per ragioni di spazio e/o di tempo). Ad occuparsi di questa tipologia di problemi è la teoria della complessità computazionale, settoriale specializzazione della teoria della computabilità che considera, appunto, le risorse di cui un calcolatore ha bisogno, come lo spazio di memoria o il tempo di esecuzione dell’algoritmo che potrebbe portarci alla soluzione desiderata. Due fattori possono essere considerati fondamentali: la lunghezza dell’input assegnato all’algoritmo in oggetto e, appunto, il tempo che esso impiega a processarlo. Con le parole di D’Agostino^xiv:

Se i dati sono costituiti da numeri, questi saranno codificati in un certo modo da una stringa di simboli che verrà data all’algoritmo come input. Questa stringa di simboli avrà una certa lunghezza n che dipende dal particolare esempio del problema P che stiamo considerando e che può essere vista come una misura della complessità di questo particolare esempio: più lunga è la stringa necessaria a codificare l’input, maggiore è la complessità dell’esempio che corrisponde a quell’input. Il tempo di esecuzione T(n) di un algoritmo misura il numero massimo di passi che un algoritmo deve eseguire per un input di lunghezza n. In altri termini, è il tempo entro il quale l’algoritmo dà una risposta per un input di lunghezza n.

La distinzione, dunque, opera sul tempo di esecuzione T(n) dell’algoritmo. Si dice che un algoritmo funziona in tempo polinomiale se la suddetta funzione è rappresentata da un polinomio di qualsiasi grado. Se invece la funzione comprende termini in cui n si trova all’esponente, l’algoritmo corrispettivo funzionerà in tempo polinomiale (i tempi di esecuzione, in questo caso, aumentano in maniera drastica anche con un lieve aumento della lunghezza dell’input). Possiamo dare le seguenti definizioni:

Un problema P è trattabile se esiste un algoritmo per risolverlo che funziona in tempo polinomiale. Altrimenti se non esiste un algoritmo per risolverlo che funziona in tempo polinomiale, il problema P si dice intrattabile^xv.

Sfortunatamente, per molti importanti problemi il migliore algoritmo ad oggi disponibile funziona in tempo esponenziale: questo rende tali algoritmi di fatto inutilizzabili. Anche se in teoria essi sarebbero in grado di dare un risultato soddisfacente al problema in oggetto, infatti, in pratica non lo fanno per una questione meramente temporale^xvi.

Che si tratti di problemi intrinsecamente non risolvibili in maniera algoritmica o di quesiti la cui risposta non arriverebbe in tempo utile, abbiamo dunque concluso che esistono de facto problemi che non possono essere risolti da un computer (poste tutte le cautele di cui abbiamo fatto cenno e considerato lo stato attuale delle ricerche). Per ulteriori approfondimenti riguardanti l’ambito qui tratteggiato, del quale abbiamo solamente sfiorato la superficie, invito a consultare innanzitutto la sezione note. L’invito di più larga portata, tuttavia, rimane affine allo spirito di questa piattaforma: affrontare le sfide del quotidiano con curiosità, cercando di farsi stupire dai concetti più semplici, per problematizzarli e manipolarli, proprio come fece lo stesso Turing, posto di fronte al problema – apparentemente semplice e di scarso interesse – del significato di calcolabilità.

Note: