Skip to main content

Infinite trees are E3 (maybe)

Not completely sure about this, but here we go: I will show that an ordered, plane recursive tree is En-computable, n3, if each vertex has its number of children bounded by an En 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:

  • δ(n) is the number of vertices of height n,
  • ι(n) is the label of the leftmost vertex of height n,
  • τ(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

δ, ι and τ are E3-computable.


Define δ, ι and τ as follows:


Note that δ(n) and ι(n) are both bounded by τ(n)+1, so we only need to show τ(n) is bounded by an E3 function.

Let σ(n)=supin(xi), an E3 function. Then τ(n)τ(n1)(σ(τ(n1))+1). 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 τ(n) is bounded by n!!. I should definitely know more about sums of series than I do.


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