Graham's Number - Definition

Definition

Using Knuth's up-arrow notation, Graham's number G (as defined in Gardner's Scientific American article) is

\left. \begin{matrix} G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\ & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\ & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\ & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\ & &3\uparrow \uparrow \uparrow \uparrow3 \end{matrix} \right \} \text{64 layers}

where the number of arrows in each layer, starting at the top layer, is specified by the value of the next layer below it; that is,

and where a superscript on an up-arrow indicates how many arrows are there. In other words, G is calculated in 64 steps: the first step is to calculate g1 with four up-arrows between 3s; the second step is to calculate g2 with g1 up-arrows between 3s; the third step is to calculate g3 with g2 up-arrows between 3s; and so on, until finally calculating G = g64 with g63 up-arrows between 3s.

Equivalently,

and the superscript on f indicates an iteration of the function, e.g., f 4(n) = f(f(f(f(n)))). Expressed in terms of the family of hyperoperations, the function f is the particular sequence, which is a version of the rapidly growing Ackermann function A(n,n). (In fact, for all n.) The function f can also be expressed in Conway chained arrow notation as, and this notation also provides the following bounds on G:

Read more about this topic:  Graham's Number

Famous quotes containing the word definition:

    “Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
    —Elaine Heffner (20th century)

    “The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
    —Jean Baudrillard (b. 1929)

    “Was man made stupid to see his own stupidity?
    Is God by definition indifferent, beyond us all?
    Is the eternal truth man’s fighting soul
    Wherein the Beast ravens in its own avidity?”
    —Richard Eberhart (b. 1904)