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)
“Wooing, wedding, and repenting, is as a Scotch jig, a measure, and a cinquepace; the first suit is hot and hasty, like a Scotch jig, and full as fantastical; the wedding, mannerly-modest, as a measure, full of state and ancientry; and then comes repentance and, with his bad legs, falls into the cinquepace faster and faster, till he sink into his grave.”
—William Shakespeare (1564–1616)
“A point has been reached where the peoples of the Americas must take cognizance of growing ill-will, of marked trends toward aggression, of increasing armaments, of shortening tempers—a situation which has in it many of the elements that lead to the tragedy of general war.... Peace is threatened by those who seek selfish power.”
—Franklin D. Roosevelt (1882–1945)