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:
“Today so much rebellion is aimless and demoralizing precisely because children have no values to challenge. Teenage rebellion is a testing process in which young people try out various values in order to make them their own. But during those years of trial, error, embarrassment, a child needs family standards to fall back on, reliable habits of thought and feeling that provide security and protection.”
—Neil Kurshan (20th century)
“We must be physicists in order ... to be creative since so far codes of values and ideals have been constructed in ignorance of physics or even in contradiction to physics.”
—Friedrich Nietzsche (1844–1900)