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:
“Nothing is so threatening to conventional values as a man who does not want to work or does not want to work at a challenging job, and most people are disturbed if a man in a well- paying job indicates ambivalence or dislike toward it.”
—Alice S. Rossi (b. 1922)
“Politics is not an end, but a means. It is not a product, but a process. It is the art of government. Like other values it has its counterfeits. So much emphasis has been placed upon the false that the significance of the true has been obscured and politics has come to convey the meaning of crafty and cunning selfishness, instead of candid and sincere service.”
—Calvin Coolidge (1872–1933)