Goodstein's Theorem - Sequence Length As A Function of The Starting Value

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:

    “It isn’t that you subordinate your ideas to the force of the facts in autobiography but that you construct a sequence of stories to bind up the facts with a persuasive hypothesis that unravels your history’s meaning.”
    —Philip Roth (b. 1933)

    “When I had mapped the pond ... I laid a rule on the map lengthwise, and then breadthwise, and found, to my surprise, that the line of greatest length intersected the line of greatest breadth exactly at the point of greatest depth.”
    —Henry David Thoreau (1817–1862)

    “No one, however powerful and successful, can function as an adult if his parents are not satisfied with him.”
    —Frank Pittman (20th century)

    “what most appals
    Is that tiny first shiver,
    That stumble, whereby
    We know beyond doubt
    They have almost run out
    And are starting to die.”
    —Philip Larkin (1922–1986)