Crea sito

La Macchina di Turing Overclockata

scritto da Profeta Incerto
nov 30

Alan Turing intuisce il Problema della Fermata

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 Goldbach1. Come si fa? Si prende una bella Macchina di Turing, la si toglie dal cellophane, la si programma a modino2, 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 concludere3 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ù problemi4, ossia – semplificando fino alla transustanziazione – che fuori dal tempo si hanno tutte le risposte5.

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. []

Tags: , , , , , , , , , , , , , , , ,

Categorie: Metafisica e Metamatica


8 Commenti a “La Macchina di Turing Overclockata”

  1. PopingaNo Gravatar scrive:

    Caro Profeta, sono un ragazzo di 14 anni che ha dei problemi con gli altri. Tutti, in classe e in compagnia, mi evitano perché dicono che faccio schifo, con i miei foruncoli e la mia puzza di cadavere decomposto. Un giorno ho persino provato a lavarmi, ma senza nessun risultato. Pensi che la Macchina Di Turing Overclockata mi possa aiutare?

  2. Profeta IncertoNo Gravatar scrive:

    Senz’altro, fedele quattordicenne brufoloso, a patto che tu riesca a tradurre la tua richiesta d’aiuto in algoritmo usando preferibilmente solo uni e zeri. Naturalmente per farlo faticherai molto e suderai e quindi puzzerai ancora di più… ma alla fine ne sarà valsa la pena.

  3. paopascNo Gravatar scrive:

    Ma il Problema della fermata ha a che fare con l’attaccarsi al tram con la mano alzata all’inizio?

  4. Profeta IncertoNo Gravatar scrive:

    Caro Pao, in effetti la prima idea per la foto era il tabellone di una fermata dell’autobus con una lunga fila di passeggeri in attesa, l’ultimo della file sta fissando con aria perplessa un altro cartello messo lì con su scritto “caduta massi”. Ma mi pareva un’idea troppo scema e alla fine ho preferito questa, molto più adatta ad un articolo scientifico.

  5. paopascNo Gravatar scrive:

    Con questo vorresti forse dire che ho fatto una domanda scema, o vater?

  6. Caro Profeta, volevo chiederti se ti andrebbe di partecipare al Carnevale della Matematica n.56 (che ospiterò il 14 dicembre sul blog Scienza e Musica) con questo bellissimo e simpatico post!

  7. Profeta IncertoNo Gravatar scrive:

    Caro Leonardo, accetto senza’altro e grazie della richiesta. Bramo solerti ceffoni dai matematici veri! PI

  8. LuigiNo Gravatar scrive:

    Caro Profeta……………..volevo scriverti un commento …ma termino subito….l’articolo mi è piaciuto!

Lascia un Commento