BUSY BEAVER - CASTORI AFFACCENDATI

È un po' una palla che il mio primo post sia di argomento matematico, ma visto che ieri sera se ne è parlato, cerco di raccontare i castori affaccendati.
Il discorso di ieri sera è nato dal fatto che, secondo me, esistono numeri molto grandi che, sebbene possano essere scritti in linea teorica, sono al di fuori della nostra portata. Ad esempio, l'universo contiene circa 4x10^79 atomi. Questo è un numero molto grande, ma con la notazione scientifica si fa in fretta a scriverlo, e lo si può associare a qualcosa di tangibile.
Invece i castori affaccendati fanno saltar fuori dei numeri veramente grandi (almeno a mio parere).
Il punto di partenza è la macchina di Turing. Si tratta di un congegno ideale (nel senso che non può essere realizzato fisicamente, ma, come direbbe qualcuno, è un ausilio per l'intelletto) la cui funzione è quella di eseguire algoritmi che qualcuno le specifica.
Il principio di funzionamento è molto semplice. La macchina è costituita da un nastro di lunghezza infinita suddiviso in caselline che possono essere riempite di 0 e 1 e da un dispositivo di lettura-scrittura che esegue le istruzioni specificate ed è in grado di leggere e scrivere il nastro. Le istruzioni vengono rappresentate come diversi "stati" nei quali il motore si può trovare. Questi stati sono in numero finito. Il tipo di istruzione è altrettanto semplice:

1. cambia stato;
2. mantieni lo stato;
3. stampa un nuovo simbolo sul nastro;
4. conserva il vecchio simbolo;
5. spostati a destra;
6. spostati a sinistra
7. fermati.

Sette istruzioni. Sembra facile. Eppure Turing ha dimostrato che un qualsiasi programma (qualsiasi programma che ci si potrebbe inventare) può essere implementato da una macchina di Turing. Di più. Turing ha dimostrato che esiste una MTU (macchina di Turing universale) alla quale possiamo passare un programma, e questa agisce simulando una macchina di Turing programmata per eseguire quel programma. Il programma stesso viene passato alla MTU mediante una certa codifica numerica scritta sul nastro. In sostanza, se scriviamo sul nastro della MTU un programma che dice "agisci come una macchina di Turing che addiziona due numeri", la MTU legge questo input, si comporta come una macchina di Turing qualsiasi, e dà l'output esatto.

Supponiamo adesso che le caselline del nastro siano tutte riempite di 0. Vogliamo passare ad una MTU un particolare programma in input in modo che l'output sia una sequenza di 1 il più lungo possibile (naturalmente vogliamo che si fermi!). Il parametro di entrata è il numero di possibili stati della macchina e il numero di 1 scritti è funzione solo di questo parametro. Se n=1, cioè il programma ha lunghezza 1, posso scrivere solo un 1, visto che devo fermarmi. Se n=2, è possibile mostrare che il numero massimo di 1 che riesco a scrivere è 4. Per n=3 è 6. Questo tipo di funzioni, che al numero di stati in input associano il numero massimo (finito) di 1 che si riesce a far scrivere a una MTU, si chiamano funzioni busy beaver. Dunque BB(1)=1, BB(2)=4, BB(3)=6. Fin qui tutti bene. Sapete quanto vale BB(12)? vale

BB(12)>=6·4096^4096^4096^...^4096

dove, tra i puntini, l'esponente 4096 viene ripetuto 166 volte.

Questo è un numero grande.

(Se non si capisce niente, ne parliamo quando ci vediamo :)

(Il libro da cui ho preso le informazioni è J.L. Casti, W. DePauli, "Gödel", Raffaello Cortina Editore)