Don't take life too seriously: it's just a temporary situation

(lettera greca omega maiuscola)

 

Si indica con Ω il numero di Chaitin.

 

Il famoso decimo problema di Hilbert consisteva nel trovare un metodo generale per risolvere un’equazione diofantea P(x1, x2, ... xn) = 0, dove P è un polinomio in n variabili.

Si conoscono algoritmi per trovare le soluzioni intere di tali equazioni in casi particolari, come i polinomi lineari o di secondo grado in due variabili, ma nel 1900 non era noto alcun algoritmo generale. Il problema è complicato dal fatto che anche con due sole variabili esistono equazioni del genere insolubili, altre con un numero finito di soluzioni e altre ancora con un numero infinito di soluzioni.

Matiyasevic riuscì infine a dimostrare che non può esistere un algoritmo capace di risolvere in un tempo finito qualsiasi equazione diofantea.

 

Successivi sviluppi portarono a dimostrare che esiste un’equazione diofantea universale P(k, x, y1, y2, ... yn) = 0 tale che al variare del parametro k le soluzioni coincidono con ogni insieme ricorsivamente enumerabile di interi positivi. La dimostrazione ha profonde conseguenze anche per l’informatica: in particolare per ogni possibile programma che scriva una sequenza di interi positivi (senza leggere nulla), esiste un valore di k per il quale l’insieme delle soluzioni intere dell’equazione coincide con l’insieme dei numeri scritti dal programma. Per esempio, esistono valori di k per i quali l’insieme delle soluzioni coincide con i numeri primi, con i quadrati, con i numeri di Fibonacci, i primi di Mersenne o di Fermat, i numeri perfetti e con ogni altro insieme citato in questo sito o che potrebbe essere generato da un qualsiasi programma su qualsiasi calcolatore.

L’esistenza di questa equazione è strettamente legata al teorema di Gödel, che afferma che in un sistema formale che contenga l’aritmetica elementare esistono infinite proposizioni vere, ma non dimostrabili, e al teorema di Turing, che afferma che non è possibile costruire un programma capace di stabilire, per qualsiasi programma fornitogli come dato, se questo si arresterà in un tempo finito o no.

 

Partendo dall’equazione universale si può definire una costante come Costante definita a partire dall'equazine universale, dove f(n) vale 1, se l’equazione ha soluzioni intere quando il parametro k vale n, 0 altrimenti. In altri termini, i bit dell’espressione della costante in base 2 dipendono dal fatto che l’equazione abbia o meno soluzioni intere per i vari valori del parametro k.

La costante è trascendente, normale e non è computabile, nel senso che non esiste algoritmo per determinarne il valore dell’n-esimo bit, dato un qualsiasi valore di n. Attenzione, questo non vuol dire che non conosciamo un algoritmo del genere, ma che non può esistere, mentre per alcuni valori di n siamo in grado di calcolare i bit corrispondenti.

La trascendenza deriva dal fatto che se Ω fosse radice di un’equazione polinomiale, sarebbe possibile calcolarne un’approssimazione con precisione arbitraria in un tempo finito.

La normalità deriva dal fatto che se alcune sequenze di bit fossero più frequenti di altre, sarebbe possibile codificarle in modo più compatto, arrivando a una compressione della costante, ossia a esprimerla con meno bit.

 

Nel 1975 Gregory J. Chaitin definì esplicitamente un’equazione diofantea esponenziale (nella quale cioè le variabili possono comparire anche come esponenti) Q(k, x, y1, y2, ... yk) = 0 e definì una costante Formula per la definizione della costante di Chaitin, dove f(n) vale 1, se l’equazione ha infinite soluzioni intere quando il parametro k vale n, 0 altrimenti.

Il metodo di Chaitin consiste nel tradurre ogni possibile programma di un calcolatore astratto nel linguaggio LISP, codificarlo quindi con un intero positivo, poi tradurre sotto forma di equazione tale programma, in modo che l’equazione abbia esattamente una soluzione in interi positivi, se il programma codificato dal parametro k si arresta, infinite soluzioni altrimenti.

 

La costante Ω esprime in un certo senso la probabilità che un calcolatore ipotetico, detto macchina di Turing universale, si arresti eseguendo un programma scelto a caso tra tutti quelli possibili, escludendo solo quelli che hanno come prefisso un programma valido più corto, ossia sono costruibili aggiungendo bit in coda a un programma di lunghezza minore.

Fissato il modello di macchina di Turing, Ω si può definire come Formula per la definizione della costante di Chaitin, dove la somma va calcolata su tutti i programmi P che si arrestano in un tempo finito e |P| è la lunghezza di P in bit.

 

Questa costante non solo non è computabile, nel senso definito sopra, ma è anche formata da bit “casuali”, nel senso che non esiste modo di “comprimerli”, a parte i primissimi bit: per qualsiasi valore di n, non esiste un programma capace di produrre i primi n bit che sia più corto di n bit. Non esiste modo di scrivere la costante di Chaitin che sia più corto che non elencarne le cifre: non esiste, per esempio, una sua espressione in termini di una serie infinita, come quelle mostrate per π, e, γ e altre costanti. Per qualsiasi calcolatore non può esistere un programma di lunghezza finita capace di generarla.

Peccato, perché la conoscenza di un numero relativamente piccolo di bit di Ω permetterebbe di risolvere un gran numero di problemi della matematica. Infatti, molti problemi tuttora irrisolti sono equivalenti al problema della terminazione di programmi relativamente corti e conoscere i primi n bit di Ω permetterebbe di stabilire se un programma P di n bit si arresta o meno. Tale programma, infatti, contribuisce per 2n al valore della costante, quindi se conoscessimo un’approssimazione Ωn di Ω con n bit sicuramente corretti, basterebbe esaminare uno per uno tutti i programmi, facendoli eseguire per intervalli di tempo crescenti, se non si arrestano prima, fino a ottenere un valore che differisca da Ωn per meno di 2n: o il programma sotto indagine si è arrestato nel frattempo, o non lo farà mai, perché aumenterebbe di troppo il valore di Ω, fornendoci la soluzione del problema associato.

Per esempio, la congettura di Goldbach asserisce che ogni numero pari maggiore di 2 si può esprimere come somma di due numeri primi. Un programma che esamini i numeri pari, arrestandosi solo se ne trova uno non esprimibile come somma di primi, è facile da scrivere e piuttosto corto, quindi nelle prime migliaia di bit di Ω si trova l’informazione se esso termina o meno e di conseguenza la conferma o la smentita della congettura.

 

Variando i dettagli del calcolatore astratto, è possibile ottenere infinite varianti di Ω, ciascuna delle quali esprime la probabilità che un programma casuale termini in un tempo finito su una specifica macchina. Sono state calcolate in questo modo alcune decine di cifre dello sviluppo binario di Ω e sono tutte 1, quindi il valore di Ω è di pochissimo inferiore a 1.

Non è un caso che i bit calcolati siano tutti 1: nell’ambito della teoria degli insiemi di Zermelo – Fraenkel con l’assioma della scelta, infatti, non si può dimostrare che un bit di Ω sia zero, quindi il calcolo delle cifre di Ω deve arrestarsi al primo 0: sappiamo che uno zero deve esserci dopo un numero finito di 1, ma non possiamo stabilire dove sia!

 

Il fatto che i primi bit siano 1 permette di comprimere, sia pur di poco, la costante con un programma relativamente semplice; nel 2000 Jürgen Schmidhuber corresse il “difetto”, definendo una costante “super-omega”, che non è comprimibile con alcun algoritmo.

 

Dato che il valore della costante dipende dal modello di macchina astratta, modificando quest’ultimo cambia il valore della costante: Soloway nel 2000 è riuscito a definire una macchina differente, tale che il primo bit della corrispondente costante è zero. Dato che nell’ambito della teoria degli insiemi non può essere dimostrato tale, abbiamo una costante della quale non potremo mai conoscere alcuna (altra) cifra!

 

Il problema della terminazione (ossia, stabilire se un dato programma con un certo input si arresti o meno) è risolubile per macchine di Turing particolarmente semplici (purtroppo inadatte a compiti realmente interessanti): è stato risolto per macchine senza input fino a 3 soli stati, è un problema aperto per macchine con 4 stati e vi sono pochissime speranze di risolverlo per macchine con un numero di stati superiore.

 

Con un modello di macchina di Turing differente nel 2000 Christian S. Calude, Michael J. Dinneen e Chi-Kou Shu calcolarono i primi 80 bit di una variante di Ω: 0.000000000000000000001000000100000010000001000001000001110010011100010100010100002. Dato che la macchina di Turing definita allo scopo utilizza 7 bit per codificare un carattere, di fatto la costante ci fornisce la probabilità che un programma per quella macchina lungo al massimo 11 caratteri si arresti.

 

Per chi fosse tentato dal cercare soluzioni dell’equazione di Chaitin, avverto che ha 17000 variabili e richiede 200 pagine per essere stampata. Sono però possibili altre formulazioni equivalenti e non è affatto escluso che se ne possa trovare una più compatta o più semplice.

Per esempio, Kieu e Ord costruirono nel 2003 un’equazione parametrica che ha un numero finito di soluzioni per ogni valore del parametro intero n: l’n-esimo bit della costante che ne deriva è 1 se il numero di soluzioni è dispari, 0 se è pari.

Bibliografia

  • Balzarotti, Giorgio;  Lava, Paolo Pietro;  103 Curiosità matematiche, Milano, Hoepli, 2010.
  • Casti, John L.;  Five Golden Rules, New York, John Wiley and Sons, 1996.
  • Chaitin, Gregory;  Metamaths, Londra, Atlantic Books, 2007.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 139, marzo 1980, pag. 108 – 112.
  • Gardner, Martin;  "Giochi matematici" in Le scienze, Milano, n. 46, giugno 1972, pag. 91 – 94.
  • Gardner, Martin;  Enigmi e giochi matematici 5, Firenze, Sansoni, 1968 -

    Traduzione di Mathematical Puzzles and Diversions, New York, Simon and Schuster, 1959.

  • Wells, David;  The Penguin Dictionary of Curious and Interesting Geometry, Londra, Penguin Books, 1991.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.