il Blog del Profeta Incerto

Oggi tratterò un argomento un po’ “tecnico”, quindi chi non capisce alzi pure la mano, e con quella ci si attacchi ben bene al tram.

Tutti sapete che quest’anno si celebra il centenario della nascita di Alan Turing, quello famoso per la tesi di Church-Turing, per il Crucituring, per il Turing Club e naturalmente per le Macchine di Turing.

Una Macchina di Turing – semplificando fino alla trivialità – è il modello astratto di ogni computer possibile, il distillato matematico dell’idea di calcolatore: per funzionare prevede un programma e dei dati di input (come un pc) solo che i calcoli non li svolge su disco o su ram bensì su di un nastro unidimensionale virtualmente infinito.

E fin qui.

Secondo un’interpretazione comunemente ritenuta vera (la tesi di Church-Turing, che forse ho già nominato prima, ah sì, all’inizio) le Macchine di Turing rappresenterebbero nientemeno che il modello di ogni possibile procedura di calcolo, cioè – semplificando fino alla mortificazione – pure voi quando calcolate vi comportate come una Macchina di Turing.

Questo significa che se un problema di calcolo non è risolvibile da una Macchina di Turing non è risolvibile in generale, e se cominciate a percepire una lontana puzza di Gödel percepite bene.

C’è ancora qualcuno?

Meglio così.

Sfioriamo ora – semplificando fino all’ignominia – il cosiddetto Problema della Fermata, o dell’Arresto.

Supponiamo di voler provare a confutare un problemuccio di teoria dei numeri tutt’ora irrisolto: la congettura di Goldbach¹. Come si fa? Si prende una bella Macchina di Turing, la si toglie dal cellophane, la si programma a modino², la si mette in moto e, infine, si aspetta.

Se l’agognato controesempio esiste (un numero pari che non è somma di due primi) state sicuri che prima o poi la Macchina lo sputerà fuori. Il problema sorge se invece quel cazzo di numero non c’è, perché in tal caso la Macchina non ce lo dirà mai: semplicemente continuerà a cercarlo. Per sempre.

E non c’è modo di sapere prima se e quando verrà il momento di gettare la spugna.

– Io la spegnerei.

– Da quanti anni aspettiamo?

– Dodicimila. Dovrei anche andare in bagno.

– E se tra due minuti lo trovasse?

– E se non lo trovasse mai?

– Nel dubbio non ci resta che aspettare.

– Hai ragione. Per caso ti ricordi anche cosa stavamo cercando?

– No.

Viene da credere che per risolvere questo tipo di calcoli occorra avere a disposizione mooolto tempo, meglio ancora infinito.

Io invece penso che il tempo sia proprio l’ostacolo essenziale. Il punto è che ce n’è troppo.

Per questo propongo la Macchina di Turing Overclockata (MDTO). Si tratta di una Macchina di Turing che computa a velocità infinita: se quando poniamo un quesito alla MDTO quella ci si mette a pensare invece che dare immediatamente la risposta vuol dire che la risposta non c’è.

Il Problema della Fermata, limite fondamentale delle Macchine di Turing tradizionali, con la MDTO di fatto non si pone proprio.

Torniamo al nostro Goldbach: se un controesempio esiste la MDTO si fermerà istantaneamente, se invece la macchina prosegue a calcolare anche solo per un secondo possiamo concludere³ che non si fermerà mai, ovvero che la congettura di Goldbach è una verità matematica.

Ora, visto che un computer che calcoli a velocità infinita non ce l’abbiamo e probabilmente non lo avremo mai, che ce ne facciamo di tutte queste belle pippe? Ma è chiaro: le usiamo per azzardare una pippa ancora più spropositata, ovvero che laddove la velocità è infinita (o se preferite laddove non si dispiega il tempo) i problemi non computabili non sono più problemi⁴, ossia – semplificando fino alla transustanziazione – che fuori dal tempo si hanno tutte le risposte⁵.

Ok, quest’ultima l’ho sparata un po’ troppo avventatamente, ma…

Ehi, chi è che sghignazza là dietro?

Ah, sei tu Dio.

Nella foto: Turing intuì il Problema della Fermata
quando i vigili gli portarono via la macchina
(e Einstein che il tempo è relativo quando
gli si fermò l’orologio, e potrei continuare).

P.S.
Questo articolo partecipa alla cinquantaseiesima copiosa edizione del Carnevale della Matematica, ospitata da Leonardo Petrillo sul suo blog Scienza e Musica.

1. Formulata nel 1742 e non ancora dimostrata, la congettura afferma che ogni numero pari maggiore di 2 può essere scritto come somma di due numeri primi. (N.d.Esegeta). [↩]
2. a) Prendi il primo numero pari non verificato, b) controlla se è somma di due numeri primi, c) se lo è passi al prossimo pari e torni al punto b. d) se non lo è ti puoi fermare, grazie. [↩]
3. Si tratta naturalmente di una conclusione non algoritmica, poiché non c’è una dimostrazione formale (N.d.Esegeta). [↩]
4. Tecnicamente i vantaggi di una Macchina del genere riguarderebbero “solo” i problemi cosiddetti semidecidibili, e non gli indecidibili – o non computabili (N.d.Esegeta). [↩]
5. Congettura del Profeta Incerto. [↩]