So suppose I have two expressions $A,B$ both consisting of some combination of parenthesis $()$, addition $+$, multiplication $\times$, exponentiation $ \text{^}$.
What is an efficient way to check if $A=B$?
My Ideas:
So immediately one thing is that we could just evaluate $A$ as a number in some base, and do the same for $B$ and then compare. The problem is that given expressions such as
$$A = (1+1)^{(1+1)^{(1+1)^{(1+1)^{(1+1)^{(1+1)}}}}}\times (1+1+1)^{(1+1+1)}+1 $$ $$ B = ((1+1)\times(1+1)+1)^{(((1+1)\times(1+1)+1))^{((1+1)\times(1+1)+1))^{((1+1)\times(1+1)+1)}}}+1 $$
This gets extremely out of hand, as the #of digits is simply too much to reasonable store. In this case: $$(1+1)^{(1+1)^{(1+1)^{(1+1)^{(1+1)^{(1+1)}}}}} = 2^{2^{2^{2^{2^{2}}}}}$$ has $2^{65536}$ digits and would be hopeless to process in this universe, by just "evaluating" the expression.
Now one thought was to modify the notion of "base-2" arithmetic to include, instead of sums of powers, say, sums of powers and power-towers, but there doesn't appear to be a natural way to generalize, and simple things like addition, and multiplication become tricky.