Esistono problemi che i computer non possono risolvere?

Informazione, intrattenimento, lavoro, educazione, soluzioni rapide a problemi complessi… in generale, abbiamo un'idea abbastanza solida di ciò che vogliamo quando usiamo un computer. Anzi, ci sono momenti in cui un sistema sembra capace di risolvere tutto, e questo ci porta a un esercizio di logica molto interessante: immagina un computer con tempo, energia e potenza di elaborazione infiniti. Esiste qualcosa che, nonostante questi vantaggi, non possa risolvere? La risposta breve è «sì», ma abbiamo bisogno dell'aiuto di Tom Scott per il resto…

Il problema della decisione

Quante volte è successo? Una domanda semplice ci getta in un buco nero di logica e ragione. Il matematico David Hilbert (quello dell'albergo infinito) rimase intrappolato in questa situazione insieme al suo collega Wilhelm Ackermann nel 1928, anno in cui entrambi presentarono la sfida dell'Entscheidungsproblem o «Problema della decisione». In termini estremamente rilassati, il problema propone quanto segue: è possibile determinare se una dichiarazione o una frase data è dimostrabile o no? Con il tempo e l'energia sufficienti, possiamo trovare la risposta a qualsiasi cosa?

Il legame con i computer

Ora, cosa c'entra questo con i computer? In realtà, quel dubbio di Hilbert può essere adattato all'universo informatico in un modo molto particolare: immagina il codice di un programma, qualsiasi programma. È possibile analizzare quel codice e determinare in modo automatico se si fermerà o entrerà in un ciclo infinito? A questo punto qualcuno suggerisce un esempio come:

10 PRINT "HOLA MUNDO"
20 GOTO 10
RUN

Ovviamente, questo pezzo di codice porta a un ciclo infinito... ma la differenza è che è stato progettato in quel modo. Determinare se alcuni programmi si fermano o continuano per sempre, questo è facile. L'idea di prendere qualsiasi codice, tutti i codici, e analizzarli per stabilire definitivamente se terminano o entrano in un ciclo può sembrare semplice in superficie, tuttavia è matematicamente impossibile. Come lo sappiamo? Grazie a un certo signore chiamato Alan Turing, e la famosa Macchina che porta il suo cognome, dell'anno 1936.

La spiegazione di Tom Scott

Qui è quando Tom Scott ci salva con la sua spiegazione: immaginiamo un programma chiamato «Halts» che può vedere un campione di qualsiasi codice e determinare se si fermerà (non abbiamo bisogno di sapere come lo fa, l'importante è che funzioni). Ancora una volta: «Halts» vede il codice e risponde «sì» (si ferma) o «no» (ciclo infinito). Ora, visualizziamo un secondo programma collegato a «Halts», che fa esattamente l'opposto della sua risposta. Cioè, se «Halts» dice che il codice si ferma, il secondo programma entra in un ciclo infinito, e se dice che entra in un ciclo, si ferma.

Questo sistema è chiamato «Opuesto», perché in sostanza fa il contrario di ciò che vi inserisci... ma è qui che Turing rompe tutto con la sua proposta: prendere il codice completo che compone «Opuesto» e fargli analizzare se stesso. Il risultato... è che non c'è risultato. È una paradosso, un'impossibilità matematica. Anche con le condizioni iniziali ideali, una minima variazione fa collassare il processo. E lì c'è la nostra risposta alla domanda originale: esiste almeno una cosa che i computer non possono e non potranno mai risolvere.