In classe con la ricorsività: una successione annidata che crescendo tende a dimezzare il valore in ingresso.
Quell’insegnante di matematica ha il vezzo di iniziare la sua lezione con domande che, alle orecchie degli alunni, suonano come vere provocazioni: interrogativi che nascondono più di quanto mostrino. Un giorno scrive alla lavagna:
\(1,\ 1,\ 2,\ 2,\ 3,\ 4,\dots\)
«Oggi» dice «chi sostiene le prove di un concorso pubblico si imbatte spesso in quesiti come questo, dove si chiede semplicemente: qual è il numero successivo?».
Un alunno, subito: «Cinque!». Un altro: «No, ancora quattro!».
Lui sorride appena, alza una mano e replica: «Lasciate stare, continuo io». E senza aggiungere altro, prolunga quella sequenza di numeri che aveva solo abbozzato:
\(1,\,1,\,2,\,2,\,3,\,4,\,4,\,4,\,5,\,6,\,7,\,7,\,8,\,8,\,8,\,8,\,9,\,10,\,11,\,12,\,12,\,13,\,14,\,14,\,15,\,15,\,15,\,16,\,16,\,16,\dots\)
Che successione strana! Non sembra affatto crescere in modo regolare. Non aumenta mai di più di una unità per volta, ma spesso lo stesso valore si ripete per diversi passi consecutivi. Il 4 compare tre volte, l’8 quattro volte, il 15 tre volte, il 16 ancora tre volte, ma senza una periodicità evidente che faccia intuire una regola semplice.
L’insegnante commenta: «Questa non è una sequenza in cui si indovina il prossimo termine. È una successione in cui bisogna capire da dove nasce il prossimo termine». Nasce da una procedura ricorsiva. La sua definizione è:
\[
a(1)=a(2)=1,\qquad
a(n)=a(a(n-1)) + a(n - a(n-1)) \quad \text{per } n>2.
\]
Ad esempio: a(3) = a(a(2)) + a(3 - a(2)) = a(1) + a(2) = 2. Essa richiama, in modo diverso, le successioni lineari di Fibonacci, le ricorrenze annidate e autoriflessive di Hofstadter, le costruzioni autoreferenziali di Conway.
Per conoscere \(a(n)\) non basta osservare i termini vicini: bisogna tornare indietro esattamente della quantità indicata dal termine precedente, leggere quel valore e affiancarlo al valore simmetrico rispetto all’indice \(n\). Ogni termine dipende da due punti della stessa sequenza, scelti dalla sequenza stessa. Nessuno, comunque, può arrivare a \(a(100)\) senza aver calcolato uno dopo l’altro tutti i 99 valori precedenti.
Cosa ci si può aspettare, allora, procedendo con la nostra ricorsione, per \(n\) abbastanza grande?
È possibile che una sequenza così irregolare, così dipendente da se stessa, finisca per rivelare un comportamento “medio” semplice e prevedibile?
La risposta, scoperta da John Conway e dimostrata da Colin Mallows, è sorprendentemente affermativa: nonostante l'apparenza caotica, il valore di \(a(n)\) tende ad agganciarsi a una frazione fissa di \(n\):
\[
\frac{a(n)}{n} \longrightarrow \frac{1}{2} \quad (n \to \infty).
\]
In altre parole, per quanto la successione possa oscillare e fermarsi, cresce in media come metà di \(n\). È come una camminata in cui si fanno tre o quattro passi in orizzontale, poi un passo in avanti, poi di nuovo due passi in orizzontale, e così via, ma alla lunga la direzione complessiva è regolare.
Mallows studiò quanto rapidamente ci si avvicina a questo valore limite e mostrò che la deviazione da \(1/2\) si restringe con una lentezza misurabile:
\[
\left|\frac{a(n)}{n} - \frac{1}{2}\right|
= O\!\left(\frac{1}{\sqrt{\log n}}\right).
\]
Dire che una quantità è \(O\!\left(\frac{1}{\sqrt{\log n}}\right)\) significa che, per valori grandi di \(n\), essa non supera un multiplo di \(1/\sqrt{\log n}\). In parole più semplici: la deviazione diminuisce, e lo fa con una velocità che è lenta, sì, ma comunque disciplinata da una struttura matematica precisa. È un modo per dire che l’irregolarità non scompare, ma viene incorniciata in un comportamento globale stabile. Questa successione è oggi ricordata come successione di Hofstadter–Conway 10.000.
L’accostamento dei due nomi riflette la sua duplice origine: da un lato le idee di Douglas R. Hofstadter sulle successioni meta-Fibonacci e sulle ricorrenze che si alimentano della propria storia, dall’altro l’analisi profonda e le dimostrazioni di John H. Conway.
L’aggiunta nel nome del numero «10.000» si deve a un episodio entrato nelle cronache matematiche. Il 15 luglio 1988, durante un colloquio ai Bell Labs, Conway presentò la sequenza dichiarando che la dimostrazione del suo comportamento asintotico era «difficilissima». Poi annunciò un premio:
- 100 dollari a chi avesse trovato un numero \(n_0\) tale che, per ogni \(n \ge n_0\), risultasse \(\bigl|\frac{a(n)}{n} - \tfrac12\bigr| < 0,05\);
- 10.000 dollari per chi avesse individuato il più piccolo di tali \(n_0\).
Neil J. A. Sloane, fondatore dell’On-Line Encyclopedia of Integer Sequences (OEIS), era seduto in prima fila a prendere appunti. Racconta che Mallows vinse la sfida, ma scelse di non incassare il premio. Sloane procedette anche a una tabulazione dei valori della successione da 1 a 10000 con il che dimostrò che a(9989) = 5365; a(9990)= 5365; a(9991)= 5366; a(9992)=5367: a(9993)= 5368; .....a(10000)=5373.
È intrigante che un meccanismo così semplice e autoreferenziale produca un andamento così irregolare e, al tempo stesso, così disciplinato da una legge asintotica limpida. La successione non procede a salti: si muove per piccoli tratti in cui il valore resta fermo, accumula, poi avanza di un’unità, poi di nuovo si arresta, come se vivessero due forze complementari: la memoria e il passo successivo.
Molti lettori, e anche alcuni matematici, hanno osservato che questa crescita sembra biologica: non lineare, intermittente, attraversata da rallentamenti e accelerazioni, eppure orientata verso una direzione riconoscibile. È forse per questo che Conway ne parlava come di un organismo matematico: qualcosa che si genera da solo, che si analizza seguendo la sua storia, e che sorprende proprio quando sembra essersi stabilizzato.
Il confronto con altre ricorrenze celebri aiuta a comprendere la natura della successione di Hofstadter–Conway.
La ricorrenza di Fibonacci è l’esempio classico di crescita regolata da una memoria fissa: ogni termine dipende sempre dagli stessi due precedenti.
La successione di Golomb introduce invece un meccanismo di autoregolazione, in cui il numero delle ripetizioni è determinato dai valori stessi della sequenza.
La successione 10.000 compie un passo ulteriore: il termine precedente decide quale parte della propria storia interrogare. La ricorrenza non è lineare, né basata su ripetizioni predefinite: è interamente auto-referenziale. Ogni nuovo valore nasce da un modo diverso di rileggere ciò che la sequenza è stata fino a quel momento.
Ridotte all’essenziale, queste tre ricorrenze mostrano tre modi di costruire ciò che viene dopo a partire da ciò che c’è ora: memoria fissa (Fibonacci), autoregolazione (Golomb), auto-referenza (Hofstadter–Conway).
Ed è in quest’ultimo caso che la definizione minima diventa davvero istruttiva: non permette di indovinare subito il termine successivo, ma obbliga a comprenderne l’origine. Non «che cosa viene dopo», dunque, ma perché.
COMMENTS