MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Question

2 use latex for tower of powers

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway 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("2→2→4

• C("1→2→3→4 ? 4→3→2") should yield "<", since 2→2→4 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?

1

# 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 chained arrow notation, indicates whether the first number is less than, greater than, or equal to the second.

Suppose the function is called C. Then

• C("2→2→4 ? 4→3→2") should yield "<", since 2→2→4 < 4→3→2,
• C("2→4→3 ? 4→3→2") should yield ">", since 2→4→3 > 4→3→2, and
• C("2→2→3 ? 2→2→2→6") should yield "=", since 2→2→3 = 2→2→2→6.

Does such a thing exist?