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:
“Other roads do some violence to Nature, and bring the traveler to stare at her, but the river steals into the scenery it traverses without intrusion, silently creating and adorning it, and is as free to come and go as the zephyr.”
—Henry David Thoreau (1817–1862)
“I feel the carousel starting slowly
And going faster and faster: desk, papers, books,
Photographs of friends, the window and the trees
Merging in one neutral band that surrounds
Me on all sides, everywhere I look.”
—John Ashbery (b. 1927)
“Th’ increasing prospect tires our wand’ring eyes.
Hills peep o’er hills, and Alps on Alps arise!
A perfect Judge will read each work of Wit
With the same spirit that its author writ:
Survey the Whole, nor seek slight faults to find
Where nature moves, and rapture warms the mind;”
—Alexander Pope (1688–1744)