# Polynomial-time algorithm to compare numbers in Conway chained arrow notation

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?

-
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 en.wikipedia.org/wiki/Fast-growing_hierarchy –  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: math.stackexchange.com/questions/72646/… –  Joel David Hamkins Feb 4 '13 at 18:10

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 )


Online javascript version: http://www.ylmass.edu.hk/~mathsclub/HyperCalc/HyperCalc.html

-
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