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?
