Skip links
Published on: Ev

B.B.+>0.533*10^14780 anni

o 4096^4096 ns: tempo impiegato da una macchina di Turing a 1GHz (che faccia 1 istruzione ogni 1ns) con 6 stati, per scrivere tutti gli “1” che riesce a scrivere, secondo il Busy Beaver Problem. Busy Beaver problem: data una macchina di Turing che si ferma, quanti “1” puo’ scrivere prima di fermarsi? Se la macchina di Turing in questione ha n stati, tale numero e’ denotato S(n) e cresce piu’ veloce di ogni funzione computabile f(n). Se la macchina di Turing ha 4 stati, scrive 13 uni, se ha 5 stati scrive almeno 4098 uni (Buntrock-Marxen beaver, 1989), se ha 6 stati scrive un numero enorme di uni, non ancora calcolato ma sicuramente > 4096^4096 (Teorema di M.W. Green, 1964).