Non so se avete mai visto il nome scritto in italiano – credo ci fosse nelle traduzioni dei giochi matematici di Martin Gardner – ma se avete un po’ di dimestichezza con l’informatica teorica dovreste sapere che cos’è il Busy Beaver. O meglio non dovreste essere sicuri di saperlo, perché ci sono due diverse definizioni. Quella originale, proposta da Tibor Rado come funzione Sigma, rappresenta il massimo numero di 1 che una macchina di Turing a n stati con due simboli (0 e 1) che termina la sua computazione può stampare. Rapido ripasso: una macchina di Turing è composta da un nastro infinito, una testina che può leggere un simbolo per volta, e un insieme di stati che sono il suo programma, perché dicono cosa può fare (scrivere un simbolo, eventualmente cancellarlo anche se nel nostro caso si suppone che il nastro contenga infiniti 0, spostarsi a sinistra o a destra ed entrare in un nuovo stato). Ci sono macchine di Turing che non terminano mai la computazione: per esempio se partiamo con un nastro pieno di zeri e abbiamo lo stato “se trovi scritto 0, scrivi 1 e vai a destra” avremo un nastro che si riempirà di 1 dal punto di partenza a destra verso l’infinito. Queste macchine non sono così interessanti, quindi per il Busy Beaver si richiede che la macchina termini l’elaborazione. La seconda definizione, indicata come BB(n), non conta gli uni scritti ma il numero massimo di passi che una macchina di Turing con n stati può compiere prima di fermarsi: anche in questo caso si richiede che la macchina effettivamente si fermi.
Possiamo trovare i primi valori di queste funzioni, come al solito, su OEIS. Per quanto riguarda la funzione Sigma, abbiamo
$$\Sigma(1) = 1; \Sigma(2) = 4; \Sigma(3) = 6; \Sigma(4) = 13; \Sigma(5) = 4098.$$
I primi valori di BB() sono invece i seguenti:
$$ BB(1) = 1; BB(2) = 6; BB(3) = 21; BB(4) = 107; BB(5) = 47176870.$$
Il valore di BB(5) è stato congetturato nel 1990 e dimostrato nel 2024: per verificarlo si sono dovute studiare 88664064 macchine di Turing e decidere se si fermano oppure no. La macchina “vincente” ha questa definizione:
0 1
A 1RB 1LC
B 1RC 1RB
C 1RD 0LE
D 1LA 1LD
E --- 0LA
La tabella si legge in questo modo: la colonna di sinistra indica in che stato si trova la macchina, la colonna centrale cosa succede se c’è scritto 0 sotto la testina e quella di destra cosa succede se c’è scritto 1; le triplette di caratteri dicono cosa scrivere (0 oppure 1), se andare a destra (R) o sinistra (L), e infine in quale stato posizionarsi. Non è mai possibile arrivare nello stato E e vedere uno 0, quindi quella casella è vuota.
E quali sono i valori successivi delle due successioni? Non solo non lo si sa ma non lo si potrà nemmeno sapere. Nel caso di Σ, sappiamo che Σ(6) > 10^^15. La notazione con doppio cappello, indicata a volte con l’esponente a sinistra ( 1510 ), è la tetrazione, la generalizzazione di moltiplicazione ed elevamento a potenza. Come 3×5 = 3+3+3+3+3 e 3^5 = 3×3×3×3×3×, 3^^5 = 3^(3^(3^(3^3)))). 10^^15 è insomma un numero così grande che è praticamente inconcepibile. Ma BB(6) è molto, molto, molto più grande: Scott Aaronson riporta che BB(6) > 2^^^5, dove il triplo cappelletto indica la pentazione, cioè il passo successivo alla tetrazione. Questo risultato surclassa il vecchio limite che era “solo” 10^^10000000. Quanto è grande quel numero? Aaronson spiega che se avessimo 10^^10000000 granelli di sabbia potremmo riempire 10^^10000000 copie dell’universo osservabile. Sì, lo stesso numero, tanto il valore è così grande che non ci si accorge della differenza. Numeri oltre ogni comprensione umana, insomma!
Cos’è una dimostrazione? Non è così semplice come sembra a prima vista, nemmeno se ci limitiamo alla matematica. Kucharski fa l’esempio di Weierstrass, che ha costruito funzioni “mostruose” facendo vedere che Cauchy aveva sbagliato le sue dimostrazioni. Ma non è la matematica il tema principale del libro: Kucharski spazia con esempi di tutti i tipi. Abraham Lincoln si mette a studiare da solo Euclide perché ritiene che anche in tribunale bisogna arrivare ad essere certi “al di là di ogni RAGIONEVOLE dubbio” ai fondamenti della statistica. Gosset (quello del test t0Student) e Pearson che sviluppano la statistica dove non si può “dimostrare” un risultato ma si può solo avere una stima di quanto esso sia coerente con l’ipotesi. I tanti esempi sul Covid (Kucharski è stato un consulente scientifico per la gestione della pandemia in UK) mostrano che spesso non abbiamo controfattuali per dimostrare che l’approccio scelto fosse il migliore. Leggendo il libro, potete vedere come la matematica non sia un sistema granitico come potrebbe sembrare a prima vista, ma qualcosa di calato nel mondo.