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:
“Reminiscences, even extensive ones, do not always amount to an autobiography.... For autobiography has to do with time, with sequence and what makes up the continuous flow of life. Here, I am talking of a space, of moments and discontinuities. For even if months and years appear here, it is in the form they have in the moment of recollection. This strange form—it may be called fleeting or eternal—is in neither case the stuff that life is made of.”
—Walter Benjamin (1892–1940)
“What though the traveler tell us of the ruins of Egypt, are we so sick or idle that we must sacrifice our America and today to some man’s ill-remembered and indolent story? Carnac and Luxor are but names, or if their skeletons remain, still more desert sand and at length a wave of the Mediterranean Sea are needed to wash away the filth that attaches to their grandeur. Carnac! Carnac! here is Carnac for me. I behold the columns of a larger
and purer temple.”
—Henry David Thoreau (1817–1862)
“The uses of travel are occasional, and short; but the best fruit it finds, when it finds it, is conversation; and this is a main function of life.”
—Ralph Waldo Emerson (1803–1882)
“The toughest thing about success is that you’ve got to keep on being a success. Talent is only a starting point in this business. You’ve got to keep on working that talent. Someday I’ll reach for it and it won’t be there.”
—Irving Berlin (1888–1989)