ASD 02 - Il Problema della Fermata

Nel precedente video avevamo introdotto alcuni dei principali concetti che si affrontano nello studio degli algoritmi. Tra questi troviamo il concetto di problema computazionale. Un problema computazionale è un problema che può potenzialmente essere risolto tramite una procedura automatica, che molto spesso prende il nome di algoritmo. Il video si era poi concluso affrontano un particolare problema computazionale: il problema della primalità. Per questo problema avevamo definito un semplice (e inefficiente) algoritmo che prendeva in input un numero intero \(n \in \mathbb{N} = \{2, 3, \ldots\}\) e ritorna come output un valore booleano, a seconda se il numero \(n\) era primo oppure no.

Quando abbiamo parlato del concetto di problema computazionale, avevamo mostrato tre particolari esempi di problema computazionale

• Il problema dell'ordinamento;

• Il problema del calcolo dei cammini minimi;

• Il problema del calcolo del minimo albero ricoprente;

come vedremo andando avanti nei video, ciascuno di questi problemi può risolto tramite un opportuno algoritmo. Prima di procedere però nel nostro studio degli algoritmi, bisogna tenere a mente il seguente, importantissimo, fatto:

Non tutti i problemi computazionali possono essere risolti tramite un algoritmo.

Detto altrimenti, esistono dei problemi che vanno oltre le nostre capacità. Non importa quanto possiamo essere bravi a definire degli algoritmi, quanto possiamo studiare ed imparare. Esistono determinati problemi che, sotto determinate ipotesi, non potranno mai essere risolti in modo automatico. Questo fatto del mondo può essere interpretato in due modi diversi:

• Da un lato l'esistenza di problemi computazionalmente irrisolubili pone dei limiti strutturali a ciò che si è in grado di fare tramite gli algoritmi.

• Dall'altro lato lo stesso limite può essere visto come il confine che separa una macchina da un essere cosciente come l'essere umano. Il fatto che noi esseri umani siamo in grado di parlare di problemi computazionalmente irrisolubili potrebbe essere utilizzato come un argomento della "superiorità" della coscienza umana rispetto ad un semplice algoritmo.

Tralasciando però queste considerazioni filosofiche, andiamo adesso a vedere in pratica un esempio di problema irrisolvibile: il problema della fermata.

Anche mettendo da parte i possibili problemi derivanti dal contesto socio-economico in cui il tipico programmatore medio è collocato, il programmare è un lavoro molto spesso frustrante e stressante. Questa frustrazione deriva principalmente dal fatto che programmare è forse una delle attività più astratte che l'essere umano, nel corso della sua evoluzione, è riuscito a praticare. Il processo di evoluzione naturale che ha sviluppato il nostro corpo e la nostra mente non ha mai considerato la possibilità di passare ore e ore davanti ad uno schermo digitale, leggendo e scrivendo sequenze di simboli nei più astrusi linguaggi di programmazione. La semplice e cruda realtà è che non siamo fatti per programmare. Per la maggior parte di noi, programmare non è una attività naturale.

Chi ha mai scritto del codice capirà immediatamente ciò che voglio dire. Il passaggio tra la scrittura del codice e l'esecuzione del programma è estremamente critico, e molto spesso è difficile capire esattamente come si comporterà il nostro programma una volta eseguito. Programmare diventa quindi un processo di trial-and-error continuo, in cui il programmatore effettua delle piccole modifiche al codice, esegue il programma, verifica se tutto va come dovrebbe andare, e continua a modificare il programma per implementare una nuova feature o sistemare un vecchio bug.

Quando un (semplice) programma viene eseguito con un certo input, tipicamente si possono verificare due comportamenti significativamente diversi tra loro:

1. Dopo un tempo finito, il programma si ferma.

2. Il programma non si ferma mai.

Un esempio del primo comportamento è dato dal programma che avevamo definito nello scorso video, e che riportiamo a seguire.

#!/usr/bin/python3

def check_primeness(n):
    result = True
    for j in range(2, n):
        if n % j == 0:
            result = False
    return result

check_primeness(10)

Quando eseguiamo tale codice, il programma dopo un po' di tempo termina e ritorna il risultato finale.

Un esempio invece del secondo tipo di comportamento, quello non terminante, è il seguente

#!/usr/bin/python3

n = 0
while True:
    n += 1
    print(n)    

Supponiamo ora di essere un programmatore che ha appena finito di modificare un programma introducendo una significativa quantità di linee di codice. Adesso, da buoni programmatori, vogliamo testare che il risultato finale del nostro duro lavoro funziona esattamente come dovrebbe. In particolare vogliamo essere sicuri che, se eseguiamo il nostro nuovo programma con un determinato input, dopo un tempo finito il nostro programma terminerà. Bene, questo è proprio quello che ci viene richiesto dal problema della fermata.

Volendo essere formali, possiamo definire il problema della fermata nel seguente modo.

Problema della fermata: Dato un programma \(P\) ed un input \(I\), vogliamo stabilire se l'esecuzione \(P(I)\) del programa \(P\) con input \(I\) termina oppure no.

Dato che il problema della fermata è un problema computazionale, potremmo inizialmente pensare di definire un algoritmo per risolvere questo problema in modo automatico. Questo approccio però non porta a nessuna strada sensata, in quanto è possibile dimostrare che il problema della fermata non può essere risolto in modo automatico. Questo significa che

Il problema della fermata è un primo esempio di problema irrisolubile

Non importa quanto possiamo provare e provare, e non importa quanto creativi e ingeniosi possiamo essere: non sarà mai possibile definire un algoritmo automatico che risolvere il problema della fermata nella sua massima generalità. Andiamo adesso a vedere il perché.