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:
“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)
“What we often take to be family values—the work ethic, honesty, clean living, marital fidelity, and individual responsibility—are in fact social, religious, or cultural values. To be sure, these values are transmitted by parents to their children and are familial in that sense. They do not, however, originate within the family. It is the value of close relationships with other family members, and the importance of these bonds relative to other needs.”
—David Elkind (20th century)