Skip to main content

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 ) \]