Sequence Length As A Function of The Starting Value
The Goodstein function, is defined such that is the length of the Goodstein sequence that starts with n. (This is a total function since every Goodstein sequence terminates.) The extreme growth-rate of can be calibrated by relating it to various standard ordinal-indexed hierarchies of functions, such as the functions in the Hardy hierarchy, and the functions in the fast-growing hierarchy of Löb and Wainer:
- Kirby and Paris (1982) proved that
- has approximately the same growth-rate as (which is the same as that of ); more precisely, dominates for every, and dominates
- (For any two functions, is said to dominate if for all sufficiently large .)
- Cichon (1983) showed that
- where is the result of putting n in hereditary base-2 notation and then replacing all 2s with ω (as was done in the proof of Goodstein's theorem).
- Caicedo (2007) showed that if with then
- .
Some examples:
| n | |||||
|---|---|---|---|---|---|
| 1 | 2 | ||||
| 2 | 4 | ||||
| 3 | 6 | ||||
| 4 | 3·2402653211 − 2 | ||||
| 5 | > A(4,4) | ||||
| 6 | > A(6,6) | ||||
| 7 | > A(8,8) | ||||
| 8 | > A3(3,3) = A(A(61, 61), A(61, 61)) | ||||
| 12 | > fω+1(64) > Graham's number | ||||
| 19 | |||||
(For Ackermann function and Graham's number bounds see fast-growing hierarchy#Functions in fast-growing hierarchies.)
Read more about this topic: Goodstein's Theorem
Famous quotes containing the words sequence, length, function and/or starting:
“We have defined a story as a narrative of events arranged in their time-sequence. A plot is also a narrative of events, the emphasis falling on causality. “The king died and then the queen died” is a story. “The king died, and then the queen died of grief” is a plot. The time sequence is preserved, but the sense of causality overshadows it.”
—E.M. (Edward Morgan)
“Baltimore lay very near the immense protein factory of Chesapeake Bay, and out of the bay it ate divinely. I well recall the time when prime hard crabs of the channel species, blue in color, at least eight inches in length along the shell, and with snow-white meat almost as firm as soap, were hawked in Hollins Street of Summer mornings at ten cents a dozen.”
—H.L. (Henry Lewis)
“Every boy was supposed to come into the world equipped with a father whose prime function was to be our father and show us how to be men. He can escape us, but we can never escape him. Present or absent, dead or alive, real or imagined, our father is the main man in our masculinity.”
—Frank Pittman (20th century)
“soon the birds and ancients
Will be starting to arrive, bereaving points
South.”
—Louise Glick (b. 1943)