Difference between revisions of "Knuth's up-arrow notation"

From Lesswrongwiki
Jump to: navigation, search
m
 
Line 1: Line 1:
 
{{wikilink}}
 
{{wikilink}}
 
 
'''Knuth's up-arrow notation''' allows to concisely represent inconceivably huge numbers. The notation is illustrated as follows:
 
'''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 = 27

Latest revision as of 03:22, 29 September 2009

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