Let $\mathcal{E}$ be the minimal set of symbolic expressions (without any predefined meaning) such that


* The symbol $x$ is in $\mathcal{E}$, and
* If expressions $P,Q\in\mathcal{E}$, then the superscript expression $(P)^{(Q)}\in \mathcal{E}$.


For every expression $S\in\mathcal{E}$, define the *interpretation* of $S$ as the function $\mathbb{R}^+\to\mathbb{R}^+$ given by $x\mapsto S$, where each occurrence of $x$ in $S$ is considered as the function parameter, and superscript expressions are considered as exponentiations. Note that we concern ourselves only with positive values of $x$.


We can make an observation that interpretations of two structurally distinct expressions can be the same function, e.g. the expressions 
$$\left((x)^{(x)}\right)^{\left((x)^{(x)}\right)},\ \left((x)^{\left((x)^{(x)}\right)}\right)^{(x)}$$
 both have the same function $x\mapsto x^{x^{x+1}}$ as their interpretation.




---


*Questions:* 


* Is there an algorithm that for every pair of expressions from $\mathcal{E}$ can decide whether they have the same interpretation?
* If yes, can we give an explicit example of such algorithm?



Is equivalence of functions built from nested exponentiations a decidable problem?
The problem is effectively decidable, and we will describe an algorithm. By way of preparation, we need to mention the o-minimality of the real exponential field, and Wilkie's solution to Tarski's High School Algebra problem.


The real exponential field $\mathbb{R}\_{exp}$ is the field of real numbers with an additional unary function $x\mapsto e^x$. Wilkie proved that $\mathbb{R}\_{exp}$ is o-minimal, meaning that that every definable set of reals is a finite union of intervals.


Note that the function $x^x$ is definable in $\mathbb{R}\_{exp}$. Indeed, $y=x^x$ if and only if 
$$\exists u\,\,(x=e^u\wedge y=e^{ux}),$$
(using $x^x=e^{x\ln x}$). Since definable functions are closed under composition, all of the tower expressions in $\mathcal{E}$ are definable in $\mathbb{R}\_{exp}$.


Now suppose two expressions $f,g\in\mathcal{E}$ define the same function on the natural numbers. Let $S$ be the set of positive real numbers $x$ for which $f(x)=g(x)$. Then $S$ is a definable subset of $R\_{exp}$. Therefore $S$ is a finite union of intervals. Since $S$ contains every positive integer, it follows that $S$ contains some interval $(x\_0,\infty)$.


But all of the functions defined by elements of $\mathcal{E}$ are analytic on $\mathbb{R}^+$. It follows immediately from 
 the principle of real analytic continuation (see e.g. Corollary 1.2.5 of A Primer of Real Analytic Functions by Krantz and Parks) that $f$ and $g$ define the same function on $\mathbb{R}^+$. 


So we are reduced to solving the identity problem for $\mathcal{E}$ interpreted over the positive integers. 
This brings us to Tarski's High School Algebra Problem and Wilkie's solution. Tarski wrote down a set of axioms for the equational theory of the structure $(\mathbb{N},\,+,\,\times,\,e,\,1)$, where $e$ is binary exponentiation. These so-called High School Axioms are the (positive) semiring axioms together with the rules of exponentiation
\begin{align\*}
&x^1=x,\,\,1^x=x\\
&(xy)^z=x^zy^z\\
%%%%%%%%%%%%%%%%%% Following Exponent rule corrected
&x^{y+z}=x^yx^z\\
&(x^y)^z=x^{yz}.
\end{align\*}
Tarski asked if the whole equational theory can be deduced from these. The answer is no. Wilkie found 'exotic' identities not deducible from the above, and he gave a computably enumerable set of identities from which the whole equational theory is indeed deducible.


Returning to identities for $\mathcal{E}$, we now have an algorithm. Given a possible identity, use Wilkie's axioms to look for it by listing all equations between elements of $\mathcal{E}$ that hold for all natural numbers. At the same time plug in integers $1,2,\ldots$ looking for a counterexample. One of these two processes will terminate after finitely many steps.


Wilkie's paper is available from CiteSeer [here.](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.9695)


There is a Wikipedia article on Tarski's High School problem [here.](https://en.wikipedia.org/wiki/Tarski%27s_high_school_algebra_problem)


It would be interesting to know if there is a nice analytic proof (avoiding Wilkie's theorem on the o-minimality of $\mathbb{R}\_{exp}$) that the functions defined on $\mathbb{R}^+$ by the expressions in $\mathcal{E}$ are determined by their values on the positive integers.


