Take the 2-minute tour ×
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|improve this question
2  
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
2  
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
2  
See also my essentially similar question at math.SE: math.stackexchange.com/questions/72646/… –  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: http://mrob.com/pub/perl/hypercalc.html#versions

Download: http://mrob.com/pub/perl/index.html

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

share|improve this answer
    
I love hypercalc, but it doesn't support Conway notation. –  khaaan Jan 21 '13 at 13:25
3  
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

 
discard

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.