Back to LessWrong

Knuth's up-arrow notation

From Lesswrongwiki

Revision as of 04:22, 29 September 2009 by PeerInfinity (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Smallwikipedialogo.png
Wikipedia has an article about

Knuth's up-arrow notation allows to concisely represent inconceivably huge numbers. The notation is illustrated as follows:

  • 3^3 = 3*3*3 = 27
  • 3^^3 = (3^(3^3)) = 3^27 = 3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3 = 7625597484987
  • 3^^^3 = (3^^(3^^3)) = 3^^7625597484987 = 3^(3^(3^(... 7625597484987 times ...)))

In other words: 3^^^3 describes an exponential tower of threes 7625597484987 layers tall. Since this number can be computed by a simple Turing machine, it contains very little information and requires a very short message to describe. This, even though writing out 3^^^3 in base 10 would require enormously more writing material than there are atoms in the known universe (a paltry 10^80).

See also