Oggi voglio parlarti dell'Alacre Castoro(*). L'Alacre Castoro (in inglese Busy Beaver) è una particolare Macchina di Turing (TM). Se sai cos'è, meglio, perché la spiegazione che segue non sarà certamente rigorosa (ma hai sempre Google a disposizione): è un sistema costituito da un programma di input finito che contiene le istruzioni e un nastro dati (infinitamente lungo in entrambe le direzioni) su cui la macchina può scrivere simboli (tipicamente 1 o 0) in funzione delle istruzioni sul nastro di input. Le istruzioni specificano che simbolo scrivere sul nastro dati e in che direzione spostarsi (destra o sinistra).
Vedendola dal punto di vista moderno (Alan Turing faceva questi ragionamenti negli anni trenta) la macchina è il più semplice calcolatore concepibile, un calcolatore ideale che è matematicamente ben definito e dal funzionamento deterministico (quindi diverso da un PC con Windows).
Le istruzioni possono mandare la macchina in loop (come ben sanno i programmatori) perciò le TM si dividono in macchine che a un certo punto si fermano e macchine che non si fermano mai. Posso costruire una TM che, dato in pasto il nastro delle istruzioni di un'altra TM, decide se questa si ferma oppure no? Turing ha dimostrato di no, il Problema della Fermata è non calcolabile, cioè non esiste un algoritmo che può decidere se la macchina si ferma o no (**) (gloria a lui).
C'è chi sostiene che questo dimostra che i cervelli sono superiori alle macchine (io intanto farei distinzione fra cervello e cervello che mi vengono in mente un paio di controesempi) ma questo non è l'argomento di oggi. L'argomento di oggi è l'Alacre Castoro, cioè la TM che alla fine si ferma e che a parità di stati (di entrate nella tabella istruzioni) riesce a fare più passi. Evidentemente l'Alacre Castoro (BB) farà un numero di passi che cresce con il numero di istruzioni della TM.
Per esempio BB(1) = 1, e BB(2) = 6, BB(3)=21. Non sembrano tanto alacri, per adesso, vero? Però Tibor Rado, nel 1962, ha dimostrato che BB() cresce più velocemente di qualsiasi funzione calcolabile:
Supponiamo di avere una funzione f(N), calcolabile, che cresca più rapidamente di BB(N), cioè f(N) > BB(N) per tutti gli N.
[Il fatto che sia calcolabile (cioè scrivibile da una TM) non sembra una grossa limitazione. Una TM può, ad esempio, aggiungere un miliardo di cifre a f(N-1), o un miliardo di miliardi ... di miliardi di cifre (dove magari i puntini ripetono "di miliardi" un miliardo di volte)]
Allora f(N) è una "Diga" per il castoro: non esiste una TM con N stati che faccia più passi di f(N). Cominciate a capire dove vado a parare, vero? A questo punto posso risolvere il Problema della Fermata, perché per scoprire se una TM a N istruzioni si ferma basta che la faccio girare fino a f(N) passi. Se non si è fermata vuol dire che non si fermerà mai più perché ha fatto più passi di BB(N) che per definizione è la TM a N istruzioni più "alacre". E visto che sappiamo che il Problema della Fermata è irrisolvibile (l'ha dimostrato Turing), f(N) non esiste. CVD
A me questa cosa è piaciuta. La cosa carina è che Beaver in inglese indica gergalmente una zona abbastanza precisa dell'anatomia femminile, quindi Busy Beaver ha un doppio senso piuttosto evidente. Se nel 1962 ci fosse stato il Moige la scienza ne avrebbe sofferto.
(*) il motivo è che mi sono capitati fra le mani alcuni vecchi "Le Scienze" dei primi anni ottanta. Uno parlava dell'Alacre Castoro, allora sono andato a cercare su Google e non ho trovato (quasi) niente. Se ti interessa l'argomento e non sai l'inglese spero di averti aiutato.
(**) la dimostrazione non è complicata (se l'ho capita io puoi capirla anche tu). La trovi nel libro "La mente nuova dell'imperatore" di Roger Penrose a partire da pag. 62. Prevede di costruire una TM Universale (UTM) che è in grado di simulare tutte le TM e con procedimento astuto (simile alla diagonalizzazione di Cantor) portarla in contraddizione sul problema della fermata. Un'altra dimostrazione è qui.
A margine aggiungo:
Se qualche gentile matematico passasse da queste parti gli/le sarei grato se mi segnalasse eventuali errori.
10:30:54 PM 
|
