17
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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 $\endgroup$
    – Goldstern
    Jan 21, 2013 at 13:16
  • 2
    $\begingroup$ 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. $\endgroup$
    – Boris Bukh
    Feb 4, 2013 at 16:24
  • 2
    $\begingroup$ See also my essentially similar question at math.SE: math.stackexchange.com/questions/72646/… $\endgroup$ Feb 4, 2013 at 18:10

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I love hypercalc, but it doesn't support Conway notation. $\endgroup$
    – khaaan
    Jan 21, 2013 at 13:25
  • 3
    $\begingroup$ 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. $\endgroup$
    – Charles
    Mar 5, 2013 at 0:31
  • $\begingroup$ The example numbers given in this answer are tiny in comparison with what one can easily write in the Conway notation. $\endgroup$ Jul 31, 2013 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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