Welcome to MathOverflow

Question

16

1

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 < 4²⁵⁶ = 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) > 4²⁵⁶ = 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?

edited Jan 21 at 12:30

asked Jan 21 at 9:58

khaaan
161●4

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 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 at 16:24

2

See also my essentially similar question at math.SE: math.stackexchange.com/questions/72646/… – Joel David Hamkins Feb 4 at 18:10

joro · Answer 1 · 2013-01-21 13:10:49Z UTC

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.