How long does the slow inefficient algorithm for computing the product in classical Laver tables take?

Question

Let $(A_{n},*)$ denote the $n$-th classical Laver table. Let $X_{n}$ be the set of all finite sequences of elements from $A_{n}$.

Define a function $E_{n}:X_{n}\rightarrow X_{n}$ by letting

1. $E_{n}((x))=(x)$.

2. $E_{n}((2^{n},x_{1},...,x_{k}))=(x_{1},...,x_{k})$

3. $E_{n}((x,1,x_{1},...,x_{k}))=(x+1,x_{1},...,x_{k})$ whenever $x_{1},...,x_{k}\in A_{n}$ and $x<2^{n}$

4. $E_{n}((x,y,x_{1},...,x_{k}))=(x,y-1,x+1,x_{1},...,x_{k})$ whenever $x<2^{n}$ and $y>1$.

The motivation behind the function $E_{n}$ is that if $E_{n}(x_{1},...,x_{r})=(y_{1},....,y_{s})$, then $(...(x_{1}*x_{2})...)*x_{r}=(...(y_{1}*y_{2})...)*y_{s}$. Furthermore, for all $x_{1},...,x_{r}$, there is some $m$ with $E_{n}^{m}(x_{1},...,x_{r})=((...(x_{1}*x_{2})*...)*x_{r})$. Therefore, the function $E_{n}$ represents going to a next step in an algorithm that computes the classical Laver tables (and this algorithm is simply an application of the double recursive definition of the classical Laver tables). Although this algorithm has no practical uses, a modification of this algorithm can be used to calculate Laver tables.

Let $t_{n}$ be the least natural number such that $E_{n}^{t_{n}}((x,y))=(x*y)$ whenever $x,y\in A_{n}$. The motivation behind the number $t_{n}$ is that $t_{n}$ measures the number of steps it takes to compute the product $x*y$ in $A_{n}$.

We have $t_{0}=1,t_{1}=3,t_{2}=145$ and $t_{3}=599$ and $t_{4}>15000000$.

Can anyone give any good bounds on the function $n\mapsto t_{n}$? Is the function $n\mapsto t_{n}$ primitive recursive?

Answer 1

Let $m=2^n$ for simplicity. Then the worst input pair seems to be $(1,m-1)$, in which case the number of steps is roughly on the order of $m!/2^m$. Meaning, although the algorithm is quite inefficient, still the number of steps is boringly small compared to non-primitive recursive functions.

Analysis:

If we start with the pair $(m-1,k)$, then after $k-1$ steps we get to $(m-1,1,m^{(k-1)})$ (where $j^{(i)}$ denotes $j,j,\ldots,j$, with $i$ repetitions), then one more step gives $(m^{(k)})$, and then $k-1$ more steps give $(m)$. Total: $2k-1$ steps. Had we started with the tuple $(m-1,k, \overline x)$ for some tuple $\overline x$, then after $2k$ steps we would have eliminated the first two entries and reached $(\overline x)$.

Similarly, if we start with $(m-2, k)$, then after $k-1$ steps we get to $((m-1)^{(k)})$. Then by the previous paragraph, each pair of $(m-1)$'s takes $2(m-1)$ steps to eliminate. (The final result of the computation depends on whether $k$ is even or odd, but we only care about the running time so this is a minor issue.) Total: Roughly $2(m-1)\cdot k/2 \approx (m-1)k$ steps.

If we start with $(m-3, k)$, then after $k-1$ steps we get to $((m-2)^{(k)})$. By the preceding paragraph, each pair of $(m-2)$-s takes roughly $(m-1)(m-2)$ steps to eliminate. Total: Roughly $(m-1)(m-2)\cdot k/2$.

And so on. At stage $i$ of the argument, we replace $k$ by $m-i$ and we multiply by $k/2$. Therefore, at the end we get roughly $(m-1)!/2^{m-2}$, as claimed.

By the way, the technique that would turn your inefficient algorithm into an efficient one is called dynamic programming or "memoizing". It consists of storing the previously computed results so we don't have to compute them again. For example, with dynamic programming we can compute $F_n$, the $n$-th Fibonacci number, in roughly $n$ steps, whereas if we blindly recompute all intermediate results over and over again, the number of steps is roughly $F_n$. (!)