Known Values
The function values for Σ(n) and S(n) are only known exactly for n < 5. The current 5-state busy beaver champion produces 4,098 1s, using 47,176,870 steps (discovered by Heiner Marxen and Jürgen Buntrock in 1989), but there remain about 40 machines with non-regular behavior which are believed to never halt, but which have not yet been proven to run infinitely. At the moment the record 6-state busy beaver produces over 1018267 1s, using over 1036534 steps (found by Pavel Kropitz in 2010). As noted above, these busy beavers are 2-symbol Turing machines.
Milton Green, in his 1964 paper "A Lower Bound on Rado's Sigma Function for Binary Turing Machines", constructed a set of Turing machines demonstrating that
where is Knuth up-arrow notation and A is Ackermann's function.
Thus
(with 327 = 7,625,597,484,987 terms in the exponential tower), and
where the number g1 is the enormous starting value in the sequence that defines Graham's number.
In contrast, the current bound on Σ(6) is 1018267, which is greater than the lower bound 33=27 (which is tiny in comparison). In fact, it is much greater than the lower bound :, which is Green's bound for .
Read more about this topic: Busy Beaver
Famous quotes containing the word values:
“During our twenties...we act toward the new adulthood the way sociologists tell us new waves of immigrants acted on becoming Americans: we adopt the host culture’s values in an exaggerated and rigid fashion until we can rethink them and make them our own. Our idea of what adults are and what we’re supposed to be is composed of outdated childhood concepts brought forward.”
—Roger Gould (20th century)
“Despite the hundreds of attempts, police terror and the concentration camps have proved to be more or less impossible subjects for the artist; since what happened to them was beyond the imagination, it was therefore also beyond art and all those human values on which art is traditionally based.”
—A. Alvarez (b. 1929)