Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less than, greater than, or equal to the second.

Suppose the function is called C. Then

  • C("1→2→3→4 ? 4→3→2") should yield "<", since 1→2→3→4 = 1 < 4256 = 4→3→2,
  • C("2→4→3 ? 4→3→2") should yield ">", since 2→4→3 = $2^{2^{\cdot^{\cdot^2}}}$ (a tower of exponents of height 65536) > 4256 = 4→3→2, and
  • C("2→2→3 ? 2→2→2→6") should yield "=", since 2→2→3 = 4 = 2→2→2→6.

Does such a thing exist?

share|cite|improve this question
If a knowledgable person reads this, perhaps he or she could also improve the linked article in wikipedia, which is full of examples but does not explain how the linked arrow notation compares with other fast growing hierarchies (Wainer, Veblen, etc.) See – Goldstern Jan 21 '13 at 13:16
Perhaps a more interesting question would be to ask for a polynomial-time decision algorithm for quantifier-free formulas in the language of fields with Conway's arrow notation. In other words, we also allow the four standard arithmetic operations in addition to the Conway's notation. – Boris Bukh Feb 4 '13 at 16:24
See also my essentially similar question at math.SE:… – Joel David Hamkins Feb 4 '13 at 18:10

1 Answer 1

Not sure this will do the job, but try Robert Munafo's hypercalc, the moto is:

Go ahead -- just TRY to make me overflow!

Hypercalc can work with quite big numbers, here is a sample session:

C1 = scale=100
C1 = 27^(86!) - (27^86)!
R1 = 10 ^ (3.467778644301262713584883219782046054843086208195414740688065133320263642461739090290922141022702407 x 10 ^ 130 )

Home page:


Online javascript version:

share|cite|improve this answer
I love hypercalc, but it doesn't support Conway notation. – khaaan Jan 21 '13 at 13:25
Robert Munafo writes that he knows Hypercalc cannot compute an ordering (or even a partial ordering) for chained-arrow notation, but he would love to learn of an algorithm that does. – Charles Mar 5 '13 at 0:31
The example numbers given in this answer are tiny in comparison with what one can easily write in the Conway notation. – Joel David Hamkins Jul 31 '13 at 18:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.