Un gioco da bambini che finisce male
Immaginate una regola semplice: prendete 1, moltiplicate per 2, aggiungete 1, moltiplicate per 2, aggiungete 1… Ricominciate. Dopo dieci passaggi ottenete un numero ragionevole. Dopo cento, la calcolatrice segnala un errore. Dopo mille, nessun computer sulla Terra può memorizzare il risultato. Eppure la regola è di una banalità disarmante. Che cosa accade davvero?
Questo genere di vertigine aritmetica non è solo una curiosità da ricreazione matematica. Tocca qualcosa di profondo: i limiti di ciò che la matematica può conoscere di sé stessa. E al centro di questa storia c’è un oggetto tanto affascinante quanto inquietante — la funzione Busy Beaver.
Quando la tartaruga supera il razzo
Per capire perché alcuni numeri sono «troppo grandi» per la matematica, occorre anzitutto comprendere che cosa significhi calcolabile. Una funzione si dice calcolabile se una macchina — un computer dotato, in teoria, di memoria e tempo illimitati — può produrne il risultato in un numero finito di passaggi. L’addizione è calcolabile. Anche la moltiplicazione. Persino funzioni che crescono a una velocità prodigiosa, come la funzione di Ackermann — che impila esponenziali su esponenziali — restano calcolabili: lente da ottenere, certo, ma accessibili in linea di principio.
La funzione Busy Beaver, invece, gioca in un’altra categoria. Introdotta dal matematico Tibor Radó nel 1962, pone una domanda apparentemente innocente: fra tutte le macchine di calcolo (chiamate macchine di Turing) dotate esattamente di n stati interni, qual è quella che si arresta dopo aver scritto il maggior numero di simboli sul proprio nastro? Questo massimo, indicato con BB(n), è il valore della funzione Busy Beaver per n.
Una macchina di Turing, per chi non è del mestiere, è un modello teorico di computer: legge e scrive simboli su un nastro infinito, seguendo regole precise a seconda del proprio stato interno. È il modello astratto su cui poggia tutta l’informatica moderna. Più stati ha una macchina, più può compiere operazioni complesse.
Risultato: BB(1) = 1. BB(2) = 6. BB(3) = 21. BB(4) = 107. E BB(5)? Non lo si conosce ancora con certezza — le stime attuali lo collocano intorno a 47 milioni. BB(6) supera 10 alla potenza di 18 267 — cioè un 1 seguito da oltre diciottomila zeri. E BB(7)? Nessuno lo sa. Nessuno può saperlo.
La velocità limite dell’aritmetica
Non è una questione di potenza di calcolo insufficiente. È un limite fondamentale, della stessa natura del limite imposto dalla velocità della luce in fisica. La funzione Busy Beaver cresce più rapidamente di qualsiasi funzione calcolabile. Qualunque algoritmo inventiate, per quanto contorto, BB(n) lo supera a partire da un certo punto. È dimostrato matematicamente.
E la conseguenza è stupefacente: calcolare BB(n) per valori anche modesti di n è impossibile in linea di principio. Non «difficile». Non «lungo». Impossibile. Nessuna macchina, nessun algoritmo, nessun metodo sistematico può produrre questi valori. La funzione Busy Beaver è ciò che si definisce non calcolabile — esiste matematicamente, ma sfugge a ogni procedimento meccanico.
«La funzione Busy Beaver è come un orizzonte: sai che esiste, ma non puoi mai raggiungerlo.»
—
Gödel l’aveva annunciato
Per capire perché questo limite sia tanto profondo, occorre risalire agli anni Trenta e ai lavori di Kurt Gödel. Nel 1931 questo logico austriaco dimostrò due teoremi che scossero le fondamenta della matematica. Il primo afferma, semplificando: ogni sistema logico sufficientemente potente contiene enunciati veri che non può dimostrare. Il secondo: un sistema simile non può dimostrare la propria coerenza.
Questi teoremi di incompletezza significano che esiste una frontiera tra ciò che è vero e ciò che è dimostrabile. E la funzione Busy Beaver si trova proprio su questa frontiera — o meglio, dall’altra parte. Determinare il valore di BB(n) per n sufficientemente grandi equivale a risolvere problemi che la matematica standard — quella che usiamo ogni giorno, fondata sugli assiomi di Zermelo-Fraenkel — semplicemente non può decidere.
I ricercatori hanno mostrato di recente che alcuni valori di BB sono legati a questioni indecidibili in specifici sistemi logici. Per esempio, BB(748) — un numero di grandezza inconcepibile — è direttamente connesso alla coerenza dell’aritmetica di Peano, il sistema formale che descrive i numeri interi. In altre parole: per conoscere BB(748) occorrerebbe un sistema logico più potente dell’aritmetica stessa.
Livelli di logica impilati come bambole russe
Di fronte a questi limiti, i matematici non restano con le mani in mano. Inventano nuovi contesti logici — sistemi di assiomi più forti, capaci di dimostrare di più. Ma ogni nuovo sistema incontra i propri limiti gödeliani. Occorre allora inventarne un altro, ancora più potente. E così via, all’infinito.
È un’immagine vertiginosa: la matematica non è un edificio finito, ma una torre di cui non si può mai vedere la cima. Ogni piano permette di vedere più lontano — e di rendersi conto che resta ancora di più da costruire.
Ciò che la funzione Busy Beaver rivela è che questa gerarchia non è astratta. È codificata in numeri concreti, nati da regole aritmetiche elementari. Addizioni, moltiplicazioni, macchine a stati. Eppure questi numeri racchiudono tutta la complessità dei fondamenti della matematica.
Concetti da portare con sé
Per chi ama la matematica
La funzione Busy Beaver BB(n) è definita come il massimo numero di «1» scritti sul nastro di una macchina di Turing con n stati che si arresta, partendo da un nastro vuoto. Una macchina di Turing con n stati è un automa finito con un alfabeto binario {0, 1}, un nastro infinito e una tabella di transizione: a ogni coppia (stato, simbolo letto) associa un simbolo da scrivere, una direzione di spostamento (sinistra o destra) e un nuovo stato (oppure l’arresto).
La non calcolabilità di BB si dimostra per riduzione al problema dell’arresto: se BB fosse calcolabile, si potrebbe decidere se una qualunque macchina di Turing si arresta — basterebbe simulare tutte le macchine con n stati fino alla soglia BB(n). Ora, il problema dell’arresto è indecidibile (Turing, 1936), dunque BB non è calcolabile.
Più precisamente, BB cresce più rapidamente di qualsiasi funzione ricorsiva totale: per ogni funzione calcolabile f : ℕ → ℕ, esiste un indice n₀ tale che per ogni n ≥ n₀, BB(n) > f(n). Questa proprietà colloca BB strettamente oltre ogni gerarchia costruttiva di funzioni a crescita rapida (gerarchia di Grzegorczyk, funzione di Ackermann ecc.).
Il legame con l’incompletezza di Gödel è formale: per un sistema assiomatico ricorsivamente enumerabile T sufficientemente espressivo, esiste un numero intero n_T tale che T non può dimostrare il valore esatto di BB(n) per n ≥ n_T. Lavori recenti hanno precisato queste soglie per sistemi come l’aritmetica di Peano (PA) o ZFC.
