Systematically Creating Ever Faster Increasing Sequences
Given a strictly increasing integer sequence/function (n≥1) we can produce a faster growing sequence (where the superscript n denotes the nth functional power). This can be repeated any number of times by letting, each sequence growing much faster than the one before it. Then we could define, which grows much faster than any for finite k (here ω is the first infinite ordinal number, representing the limit of all finite numbers k). This is the basis for the fast-growing hierarchy of functions, in which the indexing subscript is extended to ever-larger ordinals.
For example, starting with f0(n) = n + 1:
- f1(n) = f0n(n) = n + n = 2n
- f2(n) = f1n(n) = 2nn > (2 ↑) n for n ≥ 2 (using Knuth up-arrow notation)
- f3(n) = f2n(n) > (2 ↑)n n ≥ 2 ↑2 n for n ≥ 2.
- fk+1(n) > 2 ↑k n for n ≥ 2, k < ω.
- fω(n) = fn(n) > 2 ↑n - 1 n > 2 ↑n − 2 (n + 3) − 3 = A(n, n) for n ≥ 2, where A is the Ackermann function (of which fω is a unary version).
- fω+1(64) > fω64(6) > Graham's number (= g64 in the sequence defined by g0 = 4, gk+1 = 3 ↑gk 3).
- This follows by noting fω(n) > 2 ↑n - 1 n > 3 ↑n - 2 3 + 2, and hence fω(gk + 2) > gk+1 + 2.
- fω(n) > 2 ↑n - 1 n = (2 → n → n-1) = (2 → n → n-1 → 1) (using Conway chained arrow notation)
- fω+1(n) = fωn(n) > (2 → n → n-1 → 2) (because if gk(n) = X → n → k then X → n → k+1 = gkn(1))
- fω+k(n) > (2 → n → n-1 → k+1) > (n → n → k)
- fω2(n) = fω+n(n) > (n → n → n) = (n → n → n→ 1)
- fω2+k(n) > (n → n → n → k)
- fω3(n) > (n → n → n → n)
- fωk(n) > (n → n → ... → n → n) (Chain of k+1 n's)
- fω2(n) = fωn(n) > (n → n → ... → n → n) (Chain of n+1 n's)
Read more about this topic: Large Numbers
Famous quotes containing the words creating, faster and/or increasing:
“The next generation of women will enter a world in which they are perceived to have more opportunities for creating fulfilling lives than women have ever had before.”
—Elizabeth Debold (20th century)
“Faster than fairies, faster than witches,
Bridges and houses, hedges and ditches;
And charging along like troops in a battle,
All through the meadows the horses and cattle;”
—Robert Louis Stevenson (1850–1894)
“We are seeing an increasing level of attacks on the “selfishness” of women. There are allegations that all kinds of social ills, from runaway children to the neglected elderly, are due to the fact that women have left their “rightful” place in the home. Such arguments are simplistic and wrongheaded but women are especially vulnerable to the accusation that if society has problems, it’s because women aren’t nurturing enough.”
—Grace Baruch (20th century)