Il matematico ungherese Tibor Rado inventa il 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).
