# Infinite trees are ${E}_{3}$ (maybe)

Not completely sure about this, but here we go: I will show that an ordered, plane recursive tree is ${E}_{n}$-computable, $n\ge 3$, if each vertex has its number of children bounded by an ${E}_{n}$ function. So this rules out trees which grow sideways a lot quicker than they grow in height, but it has to be a lot quicker.

Let $T$ be an ordered, plane recursive tree. The height of a vertex is its geodesic distance from the root node. A breadth-first search of $T$ is a labelling of the vertices which begins at the root node, then visits all the vertices of height 1 in order (left to right), then the vertices of height 2, and so on.

Suppose there is a function $f$ such that $f\left(n\right)$ is the number of direct children of the vertex with label $n$. Then we can define the following functions:

• $\delta \left(n\right)$ is the number of vertices of height $n$,
• $\iota \left(n\right)$ is the label of the leftmost vertex of height $n$,
• $\tau \left(n\right)$ is the label of the leftmost vertex of height $n$,
• $h\left(v\right)$ is the height of the vertex with label $v$,
• $p\left(v\right)$ is the label of the parent of the vertex with label $v$.

## Lemma 1

$\delta$, $\iota$ and $\tau$ are ${E}_{3}$-computable.

### Proof

Define $\delta$, $\iota$ and $\tau$ as follows:

$\begin{array}{rcl}\delta \left(0\right)& =& 1,\\ \delta \left(n+1\right)& =& \sum _{i=\iota \left(n\right)}^{\tau \left(n\right)}.\\ \\ \iota \left(0\right)& =& 0,\\ \iota \left(n+1\right)& =& \iota \left(n\right)+\delta \left(n\right).\\ \\ \tau \left(n\right)& =& \left(\sum _{i=0}^{n}\delta \left(n\right)\right)–1.\end{array}$

Note that $\delta \left(n\right)$ and $\iota \left(n\right)$ are both bounded by $\tau \left(n\right)+1$, so we only need to show $\tau \left(n\right)$ is bounded by an ${E}_{3}$ function.

Let $\sigma \left(n\right)=\underset{i\le n}{sup}\left({x}_{i}\right)$, an ${E}_{3}$ function. Then $\tau \left(n\right)\le \tau \left(n-1\right)\cdot \left(\sigma \left(\tau \left(n-1\right)\right)+1\right)$. So it looks like this is bounded by some number of compositions of factorial, but I’m considerably less sure about that than when I began this post. Certainly, if the number of children of each vertex of height $n$ is $n!$, then $\tau \left(n\right)$ is bounded by $n!!$. I should definitely know more about sums of series than I do.

$◻$ (maybe)

Once those are defined, we can give definitions of $h$ and $p$:

$h\left(v\right)=\underset{i

$p\left(v\right)=\stackrel{\tau \left(h\left(v\right)-1\right)}{\underset{i=\iota \left(h\left(v\right)-1\right)}{\mu }}\left(\sum _{j=\iota \left(h\left(v\right)-1\right)}^{i}{x}_{j}