Don't take life too seriously: it's just a temporary situation

Busy beaver (numeri)

Teoria dell'informazione 

La traduzione letterale di “busy beaver” sarebbe “alacre castoro”, ma mi sembra troppo infelice e ho preferito mantenere il termine anglosassone.

 

Una macchina di Turing è un dispositivo ideale, utilizzato per dimostrare teoremi sulla computabilità e complessità di alcune funzioni. Nella sua forma più semplice, consiste in un nastro infinito e una testina scrivente. Il nastro è diviso in celle, ciascuna delle quali ospita un simbolo, che può essere 0 o 1. La macchina ha un certo insieme di stati ed opera a passi discreti; ogni passo consiste nel leggere il simbolo sotto la testina e, a seconda del suo valore e dello stato corrente, scrivere un simbolo, spostarsi a destra o a sinistra lungo il nastro di una cella e cambiare lo stato interno.

Esiste uno stato finale di arresto, raggiunto il quale la macchina cessa di operare, ma naturalmente non è detto che lo raggiunga: per certe combinazioni dei valori iniziali sul nastro, una macchina di Turing potrebbe operare all’infinito.

A dispetto della sua semplicità, questa macchina è equivalente a ogni calcolatore costruito o costruibile, nel senso che non esiste funzione matematica che un calcolatore reale possa calcolare e la macchina di Turing no (a parte la sua minor velocità).

 

Uno dei problemi più semplici che la macchina pone è il seguente: se iniziamo con un nastro contenente tutti zeri, qual è il massimo numero di 1 (non necessariamente consecutivi) che una macchina di Turing che si arresti può scrivere? Ignoriamo le macchine che non si arrestano, che potrebbero chiaramente scrivere infiniti 1 anche avendo pochissimi stati.

Il massimo per una macchina a n stati è detto n-esimo numero “numero busy beaver” ed è una funzione di n, indicata con Σ(n) secondo la terminologia originale di Tibor Radó, che nel 1962 dimostrò che la funzione cresce più rapidamente di qualsiasi funzione computabile e quindi in generale non è computabile in un numero finito di passi.

 

Radó definì anche una funzione S(n) come il numero massimo di passi che una macchina a n stati che si arresti possa eseguire, sempre iniziando con un nastro contenente infiniti 0.

Le due funzioni sono legate dalle seguenti diseguaglianze (Ben-Amram et al., 1996):

  • S(n) ≥ Σ(n);

  • S(n) ≤ (2n – 1)Σ(3n + 3);

  • S(n) ≤ Σ(3n + 6);

Inoltre esiste una costante c tale che Limite superiore per S(n) per n > 1 (Ben-Amram e Petersen, 2002).

 

Esistono (4n + 4)2n macchine distinte a n stati (molte delle quali equivalenti, nel senso che a partire da nastri con lo stesso contenuto produrrebbero la stessa sequenza di simboli) e la rapida crescita del loro numero rende estremamente difficile un’analisi esaustiva, anche per valori molto piccoli di n. Inoltre determinare quali si arrestino e quali no, se il nastro contiene inizialmente tutti zeri, è un problema tutt’altro che facile.

 

Per alcuni valori di n si conoscono limiti inferiori per Σ(n), ottenuti definendo esplicitamente una macchina a n stati, ma chiaramente in tali casi il record potrebbe essere battuto.

In particolare Milton Green dimostrò nel 1964 che Σ(n) > A(n – 2, n – 2) per n > 2, dove A è la funzione di Ackermann (v.).

 

L’importanza di queste funzioni è principalmente teorica, anche se la conoscenza di un numero relativamente piccolo di valori di una delle due schiuderebbe prospettive interessantissime.

Per esempio, vi sono molte congetture che potrebbero essere confutate tramite un controesempio, come la congettura di Goldbach; è possibile scrivere un programma per una macchina di Turing che vada a caccia del controesempio, in questo caso esaminando tutti i numeri pari a partire da 4, sino a trovarne uno che costituisca l’eccezione desiderata. Tale programma si arresterebbe se trovasse il controesempio e continuerebbe a lavorare all’infinito in caso contrario.

Il programma richiederebbe n stati e quindi, se si arrestasse, dovrebbe farlo entro S(n) passi. Basterebbe allora far lavorare la macchina per al massimo S(n) passi, per avere la certezza che, se non si è arrestata, non esistono controesempi.

Sfortunatamente non solo non sappiamo come calcolare S(n), tranne per pochi casi banali, ma se anche potessimo farlo la crescita rapidissima della funzione S renderebbe del tutto impraticabile l’approccio descritto.

 

La tabella riporta i valori noti.

n

Numero di macchine

Σ(n)

Passi prima dell’arresto

Autore della dimostrazione

1

64

1

1

Lin e Rado

2

20736

4

6

Lin e Rado

3

16777216

6

21

Lin e Rado

4

25600000000

13

107

Brady

5

63403380965376

≥ 4098

47176870

Heiner Marxen e Jürgen Buntrock

6

232218265089212416

≥ 3.514 • 1018267

7.412 • 1036534

Pavel Kropitz

 

7

1180591620717411303424

     

8

7958661109946400884391936

 ≥ 8.248 • 1044  

Milton Green

 

9

68719476736000000000000000000

     

10

739696442014594807059393047166976

     

11

9711967541295580042210555933809967104      

12

152784834199652075368661148843397208866816 

Limite inferiore per il numero di "1" scritti da una macchina con 12 stati

 

 

Nel caso di Σ(12) vi sono 166 esponenti 4096, uno sull’altro.

Vedi anche

Numeri di Ackermann.

Bibliografia

  • Casti, John L.;  Five Golden Rules, New York, John Wiley and Sons, 1996.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.