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?

asked Jan 21, 2013 at 9:58
$\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$ Commented 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$ Commented Feb 4, 2013 at 16:24
  • 2
    $\begingroup$ See also my essentially similar question at math.SE: math.stackexchange.com/questions/72646/… $\endgroup$ Commented 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

answered Jan 21, 2013 at 13:10
$\endgroup$
3
  • $\begingroup$ I love hypercalc, but it doesn't support Conway notation. $\endgroup$ Commented 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$ Commented 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$ Commented Jul 31, 2013 at 18:42

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.