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 peace loving nations must make a concerted effort in opposition to those violations of treaties and those ignorings of humane instincts which today are creating a state of international anarchy and instability from which there is no escape through mere isolation or neutrality.... When an epidemic of physical disease starts to spread, the community approves and joins in a quarantine of the patients in order to protect the health of the community against the spread of the disease.”
—Franklin D. Roosevelt (1882–1945)
“When the precipitancy of a man’s wishes hurries on his ideas ninety times faster than the vehicle he rides in—woe be to truth!”
—Laurence Sterne (1713–1768)
“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)