BLOG MATEMATICO di Umberto Cerruti

E' possibile consultare l'archivio degli articoli precedenti. -- Math News -- Home

28 Gennaio 2005


Indecidibilità del problema dell'arresto


Questo è il seguito del blog Alan Turing e i suoi alacri castori, del 30 novembre 2004.

Problema (informale) dell'arresto:

E' sempre possibile, dopo avere esaminato il listato di un programma P che riceve in input numeri interi, decidere se P si fermerà in un numero finito di passi, ricevuto N in ingresso?

Cominciamo con sei semplici esempi, utilizzando uno pseudocodice, che dovrebbe essere di facile comprensione per tutti.

- Esempio 1 -
input N;
x = N;
while x < 1000
print(x);
x = x+1;
end
print(x); 		entra N
a x viene assegnato il valore N
finché x è minore di 1000
scrivi x
aumenta x di 1
fine while
scrivi x

Il programma P1 dell'esempio 1 si ferma, ovviamente, per qualsiasi input N. Se N è maggiore o uguale a 1000, P1 non entra nel ciclo while, scrive N e si ferma. Se x è minore di 1000, P1 scrive N, N+1, N+2, ..., 1000 e si ferma. Per decidere che cosa fa P1 è sufficiente leggere il listato. In questo caso inoltre è anche possibile (e immediato) calcolare a priori il numero dei passi che farà il programma prima di fermarsi.

- Esempio 2 -
input N;
x = N;
while x < 1000
print(x);
x = x-1;
end
print(x); 		entra N
a x viene assegnato il valore N
finché x è minore di 1000
scrivi x
diminuisci x di 1
fine while
scrivi x

Il listato di P2 è identico a quello di P1, a parte un cambiamento di segno. Anche in questo caso chiunque può prevedere che cosa farà P2 ricevendo in input N: se N è maggiore o uguale a 1000, P1 non entra nel ciclo while, scrive N e si ferma; se invece N è minore di 1000, P1 comincia a scrivere N, N-1, N-2, ... e non si ferma più.

- Esempio 3 -
input N;
x=N;
while !isprime(3+15x)
x=x+1;
end
print(x) 		entra N
a x viene assegnato il valore N
finché 3+15x non è primo
aumenta x di 1
fine while
scrivi x

Per il programma P3 occorrono un minimo di conoscenze matematiche. Se x è 0, 3+15x vale 3, che è primo. Per qualsiasi altro valore di x, 3+15x è divisibile per 3 ed è diverso da 3, e quindi non è primo. Allora se P3 riceve un numero N non positivo, si fermerà non appena x avrà raggiunto il valore 0, e scriverà 0. Se N è positivo, P3 non uscirà mai dal ciclo while.

- Esempio 4 -
input N;
x=N;
while !isprime(2+15x)
x=x+1;
end
print(x); 		entra N
a x viene assegnato il valore N
finché 2+15x non è primo
aumenta x di 1
fine while
scrivi x

Nel caso di P4, si osserva subito una differenza sostanziale con P3: nella espressione 2+15x i numeri 2 e 15 sono coprimi, non hanno fattori comuni al di fuori di 1. Per x = 0, 1, 2, 3, 4, 5 ... 21 si ottengono i 22 interi: 

2,17,32,47,62,77,92,107,122,137,152,167,182,197,212,227,242,257,272,287,302,317
nella quale sono primi i seguenti 10: 
2,17,47,107,137,167,197,227,257,317
Evidentemente al crescere di x ci saranno percentualmente meno primi, ma è difficile pensare che ad un certo punto il rubinetto si chiuda, e non si incontri mai più un primo nella sequenza!

Chiunque scommetterebbe che, per qualsiasi N in input, P4 si fermerà dopo un certo numero di passi. Credo insomma che punteremmo tutti sulla verità della proposizione: 

Per ogni N positivo esiste un x maggiore o uguale a N tale che
2 + 15 x è primo
Ma siamo certi di vincere?

Nel 1837 Dirichlet dimostrò proprio questo risultato: 

Dati a, b coprimi nella sequenza aritmetica
a, a + b, a + 2b, a + 3b, ...
esistono infiniti primi
Dunque P4 si fermerà sempre, per qualsiasi N. Ma questa certezza risiede unicamente nella dimostrazione del citato teorema di Dirichlet, e si tratta di una dimostrazione assai difficile, certamente impossibile per la gran parte di coloro che si trovassero ad esaminare il listato dell'esempio 4, per deciderne l'arresto in tempi finiti.

Inoltre non è prevedibile il numero dei passi che P4 eseguirà prima di fermarsi, cioé la differenza tra Il numero N in input e il numero x che P4 scrive quando termina. Per esempio si ha: 

N = 10  100  1000  10000  100000  1000000
x = 11  107  1001  10005  100003  1000001
- Esempio 5 -
input N;
if N < 2
return;
end
p=prime(N);
x=1;
while mod(x2,p)!=2
x=x+1;
end
print(x); 		entra N
se N è minore di 2
termina
fine if
p diventa l'N-esimo primo
a x viene assegnato il valore 1
finché x2 diviso per p non dà resto 2
aumenta x di 1
fine while
scrivi x

P5 cerca di risolvere (con la forza bruta) l'equazione 

[E]
x2 = 2 (mod p)
dove p è l'N-esimo numero primo (si esclude il caso banale N = 1, cioé p = 2).
Per esempio se P5 riceve in input N = 4, esegue questi passi: 
P5 chiama il programma prime, passandogli 4 come argomento
p = prime(4) 
prime calcola i primi in sequenza (2, 3, 5, 7, 11, ... ) e restituisce il quarto, 
dunque p = 7
x viene inizializzato a 1
si calcola il resto r della divisione di x2 per 7
si verifica se r vale 2
se vale 2 si esce dal loop while e si scrive la soluzione x
altrimenti si incrementa x di 1 e si ricomincia:
12 = 1, resto 1
22 = 4, resto 4
32 = 9, resto 2
soluzione x = 3
Chiaramente, poiché lavoriamo modulo p, tutto si ripete ogni p passi: pertanto se nel ciclo while x arriva a p senza che si sia trovata una soluzione, questa soluzione non esiste e P5 non si fermerà mai.

In questo caso, al contrario dell'esempio 4, l'intuito aiuta poco. Facciamo qualche esperimento. Consideriamo i 22 primi con N che va da 1000 a 1021. Nella tavola sottostante, nella prima colonna si trova N, nella seconda prime(N), nella terza sì o no a seconda che 2 sia un quadrato modulo p o meno, nella quarta - solo in corrispondenza dei sì - la soluzione (minima positiva) della equazione [E]: 

[T]
1000, 7919, sì, 89                               
1001, 7927, sì, 3750
1002, 7933, no, 
1003, 7937, sì, 126
1004, 7949, no,
1005, 7951, sì, 1476
1006, 7963, no,
1007, 7993, sì, 3338
1008, 8009, sì, 3820
1009, 8011, no,
1010, 8017, sì, 1556
1011, 8039, sì, 2915
1012, 8053, no,
1013, 8059, no,
1014, 8069, no,
1015, 8081, sì, 799
1016, 8087, sì, 3553
1017, 8089, sì, 2987
1018, 8093, no, 
1019, 8101, no,
1020, 8111, sì, 887
1021, 8117, no,
E ora? Sareste disposti a scommettere 1000 euro che P5 non si ferma per N = 1022?

Con sufficiente pazienza e acume potremmo arrivare a formulare l'ipotesi che tutto dipende dal resto della divisione di p per 8 (p mod 8) in questo modo: 

[Ipotesi G]
se p mod 8 = 1 o 7 P5 si ferma
se p mod 8 = 3 o 5 P5 non si ferma
Naturalmente anche dopo moltissime prove, ci rimarrebbe sempre un piccolo dubbio. Non esisteranno poi da qualche parte un primo p della forma 8k+3 (o 8x+5) e un intero x tali che x2 mod p sia proprio 2?

In realtà la [Ipotesi G] è vera: è uno dei tanti risultati del giovane Gauss. Ancora una volta la certezza dell'arresto si basa su una non facile dimostrazione. Inoltre in questo caso non è nemmeno facile arrivare ad una ipotesi su quello P5 farà.

Anche dopo questa discussione, dato N, non si può direttamente prevedere se P5 si fermerà o meno, in quanto non si conosce alcun legame tra la posizione N di p = prime(N) nella sequenza dei primi, e il resto della divisione di p per 8.

Infine un'occhiata alla tavola [T] fa capire che non è nemmeno semplice prevedere a priori in quanti passi si ferma P5, quando si ferma (ovvero quanto è grande la soluzione minima positiva della [E]).

- Esempio 6 -
input N;
if N < 1
return;
end
x=N;
while x!=1
print(x);
if mod(x,2)!=0
x=3x+1;
else
x=x/2;
end
end
print(x); 		entra N;
se N è minore di 1
termina
fine if
a x si assegna il valore N;
finché x è diverso da 1
scrivi x;
se x è dispari
a x si assegna il valore 3x+1
altrimenti
a x si assegna il valore x/2
fine if
fine while
scrivi x

Il programma P6 genera una successione a(k) di interi, a partire da un seme a(0) = N: 

dato a(k), si calcola a(k+1) così:
se a(k) è pari allora a(k+1) = a(k)/2
se a(k) è dispari allora a(k+1) = 3 a(k) + 1
Si noti che P6 si ferma se e solo se esiste un k tale che a(k) = 1.

Le successioni così generate sono dette successioni di Collatz.

Vediamo che accade per N = 230, 231 e 232:

230,115,346,173,520,260,130,65,196,98,49,148,74,37,112,56,28,14,7,22,11,34,17,52, 26,13,40,20,10,5,16,8,4,2,1
231,694,347,1042,521,1564,782,391,1174,587,1762,881,2644,1322,661,1984,992, 496,248,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274, 137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780, 890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319, 958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367, 4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976, 488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
232,116,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

Immaginiamo che ognuna di queste tre sequenze sia data dalle altezze (misurate a intervalli costanti) raggiunte da un aquilone ideale che procede il linea retta. Possiamo allora pensare al numero dei passi del programma come alla distanza dell'aquilone dalla origine. Supponiamo che il suolo sia ad altezza 1. Con queste convenzioni possiamo dire che;

Il primo aquilone è partito da altezza 230, ha raggiunto una altezza massima di 520 ed è tornato a terra a distanza 34.
Il secondo è partito da quota 231, è arrivato a quota 9232 e ha toccato il suolo a distanza 127.
Il terzo è partito da 232 ed è rimasto sempre sotto questa altezza, terminando la corsa a distanza 21.

La Congettura di Collatz asserisce che ogni aquilone giunge a terra in un numero finito di passi. Tecnicamente: 

Il programma P6 termina sempre, per qualsiasi N positivo in input.
Si è provato, con l'uso di calcolatori, che la congettura è vera per ogni N fino a 576460752303423488. Malgrado i notevoli progressi, sia sperimentali che teorici, nessuno sa al momento se la congettura sia vera o falsa. Dunque nessuno sa dire se, assegnato un intero positivo N qualsiasi, P6 si fermerà o meno ricevendo N come input.

La discussione fatta dovrebbe convincere, a livello di buon senso, che non potrà mai esistere un programma, chiamiamolo tra di noi SuperIntender, che svolga il seguente compito: 

Presupposti:
SuperIntender si occupa di programmi P scritti in un dato linguaggio, per esempio il C.
Questi programmi, per ipotesi, ricevono come input un intero positivo N.
Compito:
SuperIntender riceve in input il listato di un programma P e un intero positivo N.
SuperIntender esamina il listato, ...., ...., ....
In un tempo finito, in tutti i casi, qualsiasi siano P ed N, SuperIntender si ferma
e stampa (sempre correttamente):
1 se P si ferma quando riceve N in input,
0 se P non si ferma.
Personalmente ritengo che si potranno avere programmi che rispondono correttamente in casi simili agli esempi 1, 2 e 3. Mi sembra molto improbabile che questo possa accadere per programmi dei tipi 4 o 5, perché si richiedono considerazioni e dimostrazioni complesse. Nel caso di programmi che facciano un lavoro simile a P6 (tipicamente la ricerca di cicli nella iterazione di funzioni) penso che un Intender non possa esistere.

Diceva Paul Erdös (non molti anni fa) che "La matematica odierna non è ancora pronta per questi problemi".

Queste però sono solo opinioni, e non dimostrazioni. Vogliamo ora provare formalmente che il problema dell'arresto è indecidibile (in altri termini: un SuperIntender non esisterà mai).

Per far questo dobbiamo ricordare alcune cose dal blog Alan Turing e i suoi alacri castori.

B(n) denota l'insieme delle macchine di Turing con n stati e due simboli. Esse sono in numero finito, precisamente: 

(4n + 4)2n
Facciamo ora partire le macchine appartenenti a B(n) sul nastro vuoto (pieno di blank), nello stato 1. Alcune di queste si fermeranno e altre no. Diciamo FERM(n) l'insieme delle macchine in B(n) che si fermano, e compiono quindi un numero finito di passi. Diciamo inoltre NFERM(n) il complementare di FERM(n) in B(n), cioé l'insieme delle macchine che, partendo sul nastro vuoto, non si fermano.

Data una macchina M che si ferma, diciamo s(M) il numero degli uno che sono sul nastro dopo che la macchina si è fermata. Poiché FERM(n) è finito, esiste il massimo degli s(M), con M che varia in FERM(n). Introduciamo la funzione di Rado: 

Definizione
å(n) = max { s(M), M Î FERM(n) }
Nel blog sopra citato abbiamo dimostrato che la funzione di Rado å(n) non è computabile. Non ci sarà mai un programma che possa, per ogni n, cacolare å(n) in tempo finito. Alcuni valori però si possono calcolare. Attualmente å(n) è noto per n = 1, 2, 3, 4. Si noti che questi calcoli non si possono fare con un procedimento di forza bruta. Non si può prendere una macchina in B(4) e farla girare e basta, tanto per vedere se e come si ferma. Ovviamente se la macchina è un elemento di NFERM(n) non sapremo mai se si ferma o meno, solo dalla osservazione. Occorre scoprire diversamente se la macchina è di un tipo o dell'altro. Per esempio, come si è già osservato, se P5 non si ferma in N passi, non si ferma più. Una analisi di questo tipo, quando possibile, può far scoprire in un tempo finito che una macchina sta in NFERM(n). Oppure per una certa macchina si posssono sperimentalmente individuare dei patterns negli 1 che scrive e in seguito dimostrare che essi si ripeteranno all'infinito, provando così che appartiene a NFERM(n). E si possono escogitare tanti altri metodi. E' un lavoro che richiede molto ingegno. Forse troppo. Infatti stiamo per dimostrare che questo lavoro non può essere fatto per tutti gli interi n.

Dimostriamo allora il nostro risultato fondamentale: 

[Teorema]
Se esiste un SuperIntender allora å(n) è computabile.


Dimostrazione
Chiamiamo S il SuperIntender che possediamo. 
Dato un n vogliamo calcolare å(n).
Le macchine di Turing in B(n) sono binarie, quindi lo stato iniziale
del nastro si può immediatamente codificare con un numero intero. 
Questo numero si interpreta come input dato alla macchina.
Nel nostro caso l'input è 0, uguale per tutte le macchine.
Si prende ora una macchina M e si passa ad S il listato di M e l'input 0.
Per ipotesi S, in un tempo finito, ci dice se M sta in FERM(n) o in NFERM(n).
Poiché B(n) è finito, in un ammontare finito di tempo veniamo a conoscere FERM(n).
Ora prendiamo M in FERM(n) e la facciamo girare finché si ferma.
Contiamo quanti 1 ci sono sul nastro: questo numero è s(M).
Facciamo questo per tutte le macchine di FERM(n).
Il massimo degli s(M) trovati è å(n).
Quindi å(n) è computabile.
Come immediato corollario otteniamo subito che non può esistere alcun SuperIntender e pertanto il problema dell'arresto è indecidibile.

In realtà noi abbiamo provato che è indecidibile il problema dell'arresto nell'insieme delle macchine di Turing binarie (con alfabeto che contiene 2 simboli) con input nullo. A maggior ragione è indecidibile il problema dell'arresto nell'insieme di tutte le macchine di Turing, con input arbitrario.

Ricordate le UTM, le Macchine di Turing Universali? Poiché una UTM può simulare qualsiasi altra macchina, è chiaro che per essa stessa il problema dell'arresto è indecidibile. Questo fatto ha alcune interessanti conseguenze di tipo epistemologico. John Conway dimostrò che nel gioco Life (di cui è lo scopritore) è possibile costruire una UTM. Da questo si può dedurre che nessun algoritmo può prevedere il destino di una generica configurazione iniziale. C'è chi vede in questo addirittura una forma di "libero arbitrio", anche se in Life di libero non c'è proprio nulla: ogni evento è rigorosamente determinato. Lo stesso Conway si spinge a chiedersi: "E' possibile, dato uno spazio di Life sufficientemente grande, inizialmente in uno stato casuale, che dopo un lungo periodo di tempo emergano animali intelligenti, autoreplicanti, e popolino certe parti dello spazio?".

E Paul Davis, nel libro "La mente di Dio" (Mondadori, 1993), a pagina 136 scrive:

da : La Mente di Dio

Alla fin fine, malgrado tutta la loro potenza, anche le UTM sono Macchne di Turing a tutti gli effetti, hanno un certo numero di stati e lavorano con un alfabeto che contiene un numero finito di simboli. E' interessante chiedersi: esistono UTM piccole?

Pascal Michel, nel 2004, ha scritto un interessante survey sull'argomento. Ecco alcuni risultati: 

Denotiamo con T(k,l) l'insieme delle macchine con k stati e l simboli.
Sono state costruite UTM nei seguenti insiemi:
TM(2,18)
TM(3,9)
TM(4,6)
TM(5,5)
TM(7,4)
TM(19,3)
TM(19,2)
Dunque nell'insieme B(19) esiste una UTM! Questo notevole risultato è dovuto a Claudio Baiocchi (2001).

Ci sono anche piccole macchine di Turing (non universali) che simulano l'iterazione della funzione di Collatz. Esse sono l'analogo del programma P6 discusso sopra. Quelle attualmente note si trovano in: 

TM(2,8)
TM(3,5)
TM(4,4)
TM(5,3)
TM(10,2)
Quindi c'è una macchina (non universale) binaria con 10 stati (un elemento di B(10)) che calcola la sequenza di Collatz. Attualmente l'unico metodo noto per dimostrare la indecidibilità del problema dell'arresto di una data macchina M consiste nel provare che M è universale. Chi riuscisse a dimostrare la indecidibilità della Congettura di Collatz avrebbe, per la prima volta, trovato una strada diversa!

18 Gennaio 2005


Ramanujan e il numero 1729


Ramanujan Srinivasa Aiyangar Ramanujan nacque il 22 dicembre 1887 nello stato di Tamil Nadu (India). Nel gennaio del 1898 entrò nella Town High School in Kumbakonam. In questo periodo capitò tra le sue mani il libro di G. S. Carr intitolato "Synopsis of elementary results in pure mathematics". Questo testo aiutò Ramanujan nella sua attività di matematico autodidatta. Già nel 1902 aveva trovato le formule risolutive delle equazioni di terzo e quarto grado. Dal 1904 si rivolse a ricerche più avanzate, come lo studio delle serie. Nel 1908 lavorava sulle frazioni continue. Malgrado il suo genio non riuscì a superare gli esami per entrare all'Università di Madras. Comunque, anche se non aveva alcun titolo di studio universitario, Ramanujan ottenne un impiego a Madras che gli consentì di proseguire le sue ricerche. Scrisse diverse lettere, contenenti alcuni dei suoi risultati, a tre matematici inglesi, tra i quali G. H. Hardy. Hardy fu l'unico a riconoscere l'importanza del lavoro che teneva tra le mani, e fece venire Ramanujan a Cambridge. Riuscirono a collaborare, anche se Ramanujan aveva un suo stile tutto particolare, del tutto non professionale. Purtroppo Srinivasa si ammalò gravemente nel 1919, morì l'anno seguente. Pubblicò alcuni splendidi lavori su riviste specializzate, ma lasciò al tempo stesso un tesoro matematico in una serie di quaderni di appunti. Si tratta di osservazioni e teoremi spesso non del tutto dimostrati. Grazie all'attività decennale (1985 - 1997) di Berndt e dei suoi collabolatori, i "Ramanujan's notebooks" sono stati in buona parte resi disponibili ai matematici (completi di dimostrazioni). Essi sono pubblicati dalla casa editrice Springer.

Uno dei più famosi aneddoti della storia della matematica moderna narra che Hardy, recatosi a trovare Ramanujan in ospedale, tanto per dire qualcosa, osservò che il numero del taxi (1729) che aveva preso sembrava "piuttosto insulso". Al ché Ramanujan rispose immediatamente : "No Hardy, è un numero estremamente interessante: è il minimo intero che si può esprimere come somma di due cubi in due modi diversi!".

Come avrà fatto Ramanujan a vedere così immediatamente questo fatto? Personalmente condivido l'opinione di Littlewood: "ogni intero naturale era per Ramanujan un amico personale". Dei rapporti tra Hardy e Ramanujan si può leggere nello scorcio autobiografico di G. H. Hardy "Apologia di un matematico", ristampato nel 2002 da Garzanti. La vita del grande Ramanujan è narrata nel romanzo di Robert Kanigel "L'uomo che vide l'infinito", edito da Rizzoli (2003).

In effetti si ha: 

1729 = 13 + 123 = 93 + 103
Questo fatto era stato notato per la prima volta da Bernard Frénicle de Bessy (1605-1670).

In quello che è uno dei più bei libri di teoria dei numeri che siano mai stati scritti, "An Introduction to the Theory of Numbers", gli autori (G. H. Hardy e E. M. Wrigth) dimostrano che per ogni n positivo esiste almeno un intero esprimibile come somma di due cubi in n modi diversi. Pertanto: 

Per ogni n esiste un minimo intero positivo 
che è somma di due cubi in n modi diversi.
Questo intero viene chiamato Taxicab(n).
Qui sotto c'è una tavola con i valori noti di Taxicab(n): 
Taxicab(1) = 2 (ovvio)
2 = 13 + 13

Taxicab(2) = 1729 (Frénicle, 1657)
1729 = 13 + 123
1729 = 93 + 103

Taxicab(3) = 87539319 (Leech, 1957)
87539319 = 1673 + 4363
87539319 = 2283 + 4233
87539319 = 2553 + 4143

Taxicab(4) = 6963472309248 (Rosenstiel, Dardis and Rosenstiel, 1991)
6963472309248 = 24213 + 190833
6963472309248 = 54363 + 189483
6963472309248 = 102003 + 180723
6963472309248 = 133223 + 166303

Taxicab(5) = 48988659276962496 (David W. Wilson, 1997)
48988659276962496 = 387873 + 3657573
48988659276962496 = 1078393 + 3627533
48988659276962496 = 2052923 + 3429523
48988659276962496 = 2214243 + 3365883
48988659276962496 = 2315183 + 3319543
La sequenza Taxicab(n) è la numero A011541 nella On-Line Encyclopedia of Integer Sequences.

Taxicab(6) non è noto, ma si sa che è compreso tra 1018 e 24153319581254312065344. Il limite inferiore 1018 è stato trovato da D.J. Bernstein nel 1998. Nel 2002 Randall L. Rathbun provò che 24153319581254312065344 è somma di due cubi in 6 modi diversi.

Torniamo al numero 1729. Un intero composto n si dice pseudoprimo sulla base a se n divide an-1 - 1. 1729 è il più piccolo intero che è pseudoprimo sulle basi 2, 3 e 5.

Un intero che sia pseudoprimo su tutte le basi possibili si chiama numero di Carmichael. 1729 è il terzo numero di Carmichael (i primi due sono 561 e 1105). La successione dei numeri di Carmichael è la A002997 nella On-Line Encyclopedia of Integer Sequences.

In www.mathpages.com/ si trova un'altra sorprendente proprietà del 1729. Se consideriamo il numero e, base dei logaritmi naturali, esattamente dalla cifra 1729-esima dopo la virgola si trova la sequenza 0719425863. Questa è la prima occorrenza, nella espressione decimale di e, di un blocco di 10 cifre tutte diverse!

Inoltre la somma delle cifre di 1729 è 19, e 1729 = 7 13 19, è divisibile sia per 19 che per 91.

Ken Ono, nell'articolo "Ramanujan, Taxicabs, Birthdays, Zipcodes, and Twists" (American Mathematical Monthly, 104, No. 10, 1997, pages 912-917), esamina diverse apparizioni del numero 1729, e delle sue permutazioni, nella vita stessa di Ramanujan. Sostiene insomma che le cifre 1, 7, 2, 9 hanno un particolare rilievo nella storia personale di Ramanujan. Seguiamo quanto Ken Ono dice.

Due permutazioni coinvolgono direttamente Bruce Berndt, che come si è detto sopra, ha dedicato molta parte della sua vita allo studio e alla divulgazione dei quaderni di Ramanujan. Sonja, la sorella più giovane di Bruce, è nata nel 1972. L'abitazione di Bruce è in Urbana, Illinois 61802-7219.

Cerchiamo connessioni più matematiche. In un articolo del 1916 Ramanujan scriveva:

"I numeri pari che non sono della forma x2 + y2 + 10 z2
sono i numeri 4s (16 t + 6).
I numeri dispari che non sono di questa forma sembrano non obbedire ad alcuna legge.
Tra essi si trovano:
3, 7, 21, 31, 33, 43, 67, 79, 87, 133, 217, 219, 223, 253, 307, 391"
A seguito di estensivi calcoli all'elenco dei 16 interi di Ramanujan si sono aggiunti 679 e 2719. Un formidabile e recente risultato di W. Duke and R. Schulze-Pillot prova che gli interi dispari in questione sono in numero finito. 
Potrebbe 2719 essere il più grande intero dispari 
che non si può scrivere nella forma
x2 + y2 + 10 z2?
Se volete affrontare questo problemino, chiedete aiuto a Srinivasa!

Ricordiamo, per concludere, che Ramanujan è vissuto nel periodo 1887-1920.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

30 Novembre 2004


Alan Turing e i suoi alacri castori.


Come promesso nell'ultimo blog, facciamo ancora una visita alla OEIS (On-Line Encyclopedia of Integer Sequences) che, da un paio di settimane, ha superato le 100000 voci. Se clicchiamo su Welcome, troviamo:

New Users:

Let's begin at once with an example of a sequence of great importance:
ID Number: A060843
Sequence: 1,6,21,107
Name: Busy Beaver problem: maximal number of steps that an n-state Turing
machine can make on an initially blank tape before eventually halting.
Comments: The function Sigma(n) (A028444) denotes the maximal number of tape
marks which a Turing Machine with n internal states and a two-way
infinite tape can write on an initially empty tape and then halt. The
function S(n) (the present sequence) denotes the maximal number of steps (shifts)
which such a machine can make (it needs not produce many tape marks).
Given that 5-state machines can compute Collatz-like congruential
functions (see references), it may be very hard to find the next term.
The sequence grows faster than any computable function of n, and so is
non-computable.
(.... seguono riferimenti ....)

Probabilmente non capiremo molto, di primo acchito. Forse la cosa più inquietante è che la sequenza è dichiarata non computabile. Eppure i primi quattro termini ci sono. Si può proseguire? E' solo un problema di potenza di calcolo, o c'è sotto qualcosa di più fondamentale?
Come può questa successione S(n) crescere più in fretta di qualsiasi funzione f(n) che io posso calcolare?

Procediamo con calma. Alan Turing, intanto. Chi era costui?

Alan Mathison Turing nacque a Paddington (Londra) nel 1912 e morì nei pressi di Manchester nel 1954, in circostanze poco chiare.
Fu uno studente indisciplinato, che non piaceva agli insegnati sebbene in matematica vincesse tutti premi possibili. Amava molto la chimica, ma era disapprovato dai professori, perché seguiva per gli esperimenti una scaletta tutta personale. Studiava molte cose (per conto suo), dalla relatività alla meccanica quantistica. Nel 1928 strinse una forte amicizia con Christopher Morcom, un allievo dell'anno seguente. Finalmente poteva parlare di scienza con qualcuno! Purtroppo il ragazzo morì nel 1930, e questo avvenimeneto fu per Alan un colpo durissimo.
Nel 1931 entrò al King's College di Cambridge. A Cambridge tutto fu più facile per lui, e Turing poté studiare i lavori di Russell e Von Neumann. Dopo la laurea nel 1934 seguì il corso di Max Newman sui fondamenti della matematica, nel quale si parlava dei lavori di Godel e Hilbert. Tra il 1936 e il 1937 ideò la macchina astratta che ora viene chiamata appunto "macchina di Turing", e descrisse un numero non computabile. Ottenne anche risultati importanti in teoria della probabilità e sulla funzione zeta di Riemann. Durante la guerra fu uno dei principali artefici della rottura del codice crittografico tedesco Enigma (si veda la biografia di Hodge).
Lavorò in diverse discipline, comprese la chimica e la biologia. Ancora oggi è citato un suo articolo sulla morfogenesi. Alan Turing fu tra i primi ad occuparsi di intelligenza artificiale e fu uno dei fondatori della moderna teoria della computabilità.

Vediamo ora in dettaglio che cosa è una macchina di Turing. Una macchina di Turing consta di un nastro illimitato nelle due direzioni, suddiviso in celle identiche adiacenti, e di una testina mobile. La testina può leggere e scrivere simboli nelle celle. Inoltre può spostarsi a destra o a sinistra. Il tempo è discreto: t = 0, 1, 2, ... Al tempo 0 la testina si trova in una data posizione iniziale. Quando parliamo di macchina di Turing con n stati intendiamo effettivamente dire che ci sono sono n+1 stati possibili: n stati ordinari numerati da 1 a n, più uno stato speciale che denotiamo con H (halt). Se la macchina perviene in questo stato, cessa ogni sua attività. Ma che cosa fa questa macchina? La macchina ad ogni istante t legge il simbolo x contenuto nella cella sulla quale è posizionata la testina. In funzione di x e dello stato s(t) in cui si trova fa tre cose:


L'insieme A dei simboli (o caratteri) che la macchina può leggere o scrivere contiene per ipotesi q elementi, che possono essere arbitrari (lettere o cifre della vostra tastiera, per esempio). In ogni caso A deve contenere un carattere speciale, detto blank. Quando la macchina scrive il carattere blank, cancella quello che c'è nella cella, la restituisce allo stato originario. In sostanza per noi il nastro vuoto è il nastro dove in ogni cella c'è il blank.
Denotiamo con Q l'insieme degli n stati ordinari, con QH l'insieme di tutti gli stati e con M l'insieme dei (due) possibili movimenti.
Con queste notazioni una macchina di Turing T è descritta completamente dalla funzione FT: 

[1]
FT : Q × A  --------->  QH × A × M
La corrispondenza appena evidenziata tra le macchine di Turing e le funzioni [1] permette di contare quante sono le macchine di Turing con n stati. Ricordando che 
[2]
ci sono |B||A| funzioni tra l'insieme A e l'insieme B
(dove |X| denota il numero di elementi di X)
otteniamo subito che 
[3]
ci sono (2·q·(n+1))q·n
macchine di Turing con n stati, su un alfabeto di q simboli.
E' impossibile capire veramente un'idea matematica (e le sue conseguenze) senza fare degli esempi. Sicuramente Alan Turing trascorse molte ore con carta e penna (se non faceva tutto nella mente) per simulare il comportamento delle sue amate macchinette. Ora ci viene in aiuto il computer. Io ho utilizzato una bellissima applet creata da Suzanne Skinner. Potete trovarla qui con le istruzioni per l'uso.

Utilizzerò nel seguito le stesse convenzioni di Suzanne Skinner. Tutti i programmi per la macchina di Turing che seguono, girano effettivamente sulla sua applet.

[4]
Un Turing-programma è una lista finita di quintuple r1, r2, r3, r4, r5 dove:

Inoltre conveniamo che:
Ad ogni passo la macchina T si trova in un determinato stato r1 e legge il simbolo r2 contenuto nella cella sulla quale è posizionata la testina. Allora T va a cercare la riga che inizia con r1, r2 e, conseguentemente, passa nello stato r3, sostituisce r2 con il simbolo r4, si sposta a destra di una cella se r5 è > oppure si sposta a sinistra se r5 è <.

Utilizzando la [1] quanto detto si può riassumere in 

FT(r1, r2) = (r3, r4, r5)
Per definire completamente la funzione FT, e quindi la relativa macchina di Turing a n stati su un alfabeto di q simboli, occorre scrivere q · n quintuple. In certi casi però possiamo sapere a priori che, nel corso del calcolo, alcune coppie simbolo-stato non si presenteranno. Più in generale vogliamo che un Turing-programma sia accettato come valido indipendentemente dal numero di quintuple che contiene. Facciamo pertanto la seguente convenzione: 
[5]
Se al tempo t la macchina legge il simbolo u e si trova nello stato v
e non esiste nel programma alcuna riga che inizia con u, v allora
la macchina si ferma: non scrive nulla e non si sposta più.
Cosideriamo per esempio il seguente Turing-programma: 
[6]
1,_,1,_,>
Questa istruzione suona così: "Se il nastro è vuoto e sono nello stato 1 allora lascio il nastro vuoto, rimango nello stato 1 e mi sposto a destra di una casella".
Poiché ogni macchina deve avere almeno uno stato (lo stato 1), e il blank _ è sempre in A, questo programma di una riga può girare su qualsiasi macchina di Turing. Se passiamo questo programma ad una macchina T, possono accadere sostanzialmente tre cose: