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 \geq 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(n)$$ is the number of direct children of the vertex with label $$n$$. Then we can define the following functions:

• $$\delta(n)$$ is the number of vertices of height $$n$$,
• $$\iota(n)$$ is the label of the leftmost vertex of height $$n$$,
• $$\tau(n)$$ is the label of the leftmost vertex of height $$n$$,
• $$h(v)$$ is the height of the vertex with label $$v$$,
• $$p(v)$$ 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{eqnarray*} \delta(0) &=& 1, \\ \delta(n+1) &=& \sum_{i=\iota(n)}^{\tau(n)}. \\ \\ \iota(0) &=& 0, \\ \iota(n+1) &=& \iota(n) + \delta(n). \\ \\ \tau(n) &=& \left (\sum_{i=0}^n \delta(n) \right ) – 1. \end{eqnarray*}$

Note that $$\delta(n)$$ and $$\iota(n)$$ are both bounded by $$\tau(n)+1$$, so we only need to show $$\tau(n)$$ is bounded by an $$E_3$$ function.

Let $$\sigma(n) = \underset{i \leq n}{\sup}(x_i)$$, an $$E_3$$ function. Then $$\tau(n) \leq \tau(n-1) \cdot \left ( \sigma(\tau(n-1)) + 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(n)$$ is bounded by $$n!!$$. I should definitely know more about sums of series than I do.

$$\square$$ (maybe)

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

$h(v) = \underset{i \lt v}{\mu} (v \leq \tau(i))$

$p(v) = \overset{\tau(h(v)-1)}{\underset{i=\iota(h(v)-1)}{\mu}} \left ( \sum_{j=\iota(h(v)-1)}^i x_j \lt v-\iota(h(v)) \right )$