Lists and finite trees are $E_{3}$

2010-07-16

In order to prove the fgoagog thing we need to be able to do computations on trees at a low level of the Grzegorczyk hierarchy, so it doesn’t mess up the complexity of the whole group computation. I will give a model of finite trees that lies in $E_{3}$ , the same level as Cannonito/Gatterdam’s standard index for the free group. (( this post has been sitting as a draft since the beginning of May because I wanted to make some nice tree pictures, but I’d rather just publish it now. So, the trees section is copied out of my notes and might not make sense ))

Lists

First of all, I’ll show how to encode sequences of numbers so that they can be manipulated and read by $E_{3}$ functions. Let $(x_{1}, \dots, x_{n})$ be a sequence of $n$ non-negative numbers.

First encode the list as a Gödel number:

$e n c o d e (x_{1}, \dots, x_{n}) = x = \prod_{i = 1}^{n} (p_{i})^{x_{n} + 1},$

where $p_{i}$ is the $i^{th}$ prime. (( it’s just occurred to me that I haven’t shown that things such as finding primes and divisiblity tests and so on are $E_{3}$ computable. I’ll do another post after this one with suitable definitions for all that stuff ))

In order to actually do anything with this encoded list, we need to be able to find out its length and the value of the entry at any given position. $p l o g (x, p)$ return the exponent of the prime $p$ in $x$ :

$\begin{array}{rcl} p l o g (x, p) & = & {\begin{array}{lr} 1 + p l o g (\frac{^{'}^{'} x}{p}, p), & p ∤ x, \\ 0, & p ∤ x . \end{array} \\ (x)_{i} & = & p l o g (x, p_{i}) - 1 \end{array}$

I’m using $(x)_{i}$ instead of $x_{i}$ to denote the $i^{th}$ element of an encoded list, just so it’s clear that’s what’s happening later on.

$l h (x)$ finds the length of an encoded list:

$l h (x) = \underset{i \leq x}{μ} ((p_{i} ∤ x) - 1)$

Note that $\underset{i \leq x}{μ} P (i) = x + 1$ if there is no $i \leq x$ such that $P (i)$ holds. The $i \leq x$ bit in the minimisation is so that the function is bounded – it doesn’t matter what upper bound I pick as long as it’s “enough”.

$f i n d (x, n)$ returns the first occurence of $n$ in an encoded list $x$ :

$f i n d (x, n) = \underset{i \leq x}{μ} (x)_{i} = n$

Make use of $f i n d$ to determine whether an encoded list contains a given value:

$c o n t a i n s (x, n) \Leftrightarrow (x)_{f i n d (x, n)} = n$

This function to find the largest element of a list $x$ , $b i g g e s t (x)$ , is defined by using a helper function $b i g g e s t^{'} (x, n)$ , which gives the biggest element up to $(x)_{n}$ :

$\begin{array}{rcl} b i g g e s t (x) & = & b i g g e s t^{'} (x, l h (x)) \\ b i g g e s t^{'} (x, 0) & = & (x)_{0} \\ b i g g e s t^{'} (x, n + 1) & = & max ((x)_{n + 1}, b i g g e s t^{'} (x, n)) \end{array}$

$s l i c e (x, s, e)$ , which I will also write $x [s \dots e]$ , gives you the sublist of $x$ starting at position $s$ and ending at position $e$ . The max/min stuff is to make sure this function works sensibly even when given wrong inputs:

\[ $\begin{array}{rcl} s l i c e (x, s, e) & = & \prod_{i = s^{'}}^{e^{'}} (p_{i + 1 - s^{'}})^{(x)_{i} + 1} \\ e^{'} & = & max (1, min (e, l h (x))) \\ s^{'} & = & max (1, min (s, e^{'})) \end{array}$

$s p l i c e (x, n)$ , also written $x : n$ , appends a value $n$ to the end of an encoded list $x$ :

$s p l i c e (x, n) = x \cdot p_{l h (x) + 1}^{n + 1}$

Trees

A tree consists of a set of vertices $V$ and a set of edges $E$ connecting pairs of vertices, with no loops.

A rooted tree has a unique vertex $v_{0}$ said to be at the ‘top’. In an ordered tree, the set of children of each vertex is ordered, so there is a leftmost child, and so on. A plane recursive tree is a rooted, ordered tree constructed by a process which begins with the root node and recursively adds vertices below existing ones.

We can assign a labelling to a plane recursive tree by giving vertices labels corresponding to the order in which they were added to the tree, beginning with $0$ for the root. This way, the sequence of labels encountered heading outwards from the root is always increasing. Every edge can also be given a unique labelling by saying that the edge $e_{i j}$ , connecting vertex $v_{i}$ to $v_{j}$ , has label $max (i, j)$ .

Suppose we have a tree $T = (V, E)$ with root vertex $v_{0}$ . $T$ is $E_{n}$ computable if there is an $E_{n}$ -decidable labelling $i : V \to N$ (we can assume $i (v_{0}) = 0$ ) and an $E_{n}$ -computable “parent function” $p_{T} : i (V) \to i (V)$ which gives the label of the parent of a vertex. We also require that $p_{T} (v_{0}) = 0$ .

A finite plane recursive tree can be entirely described in a canonical way by a depth-first walk. Note that every node has a single parent and a finite ordered set of children. The process on ‘visiting’ a vertex $v_{i}$ goes as follows: for each child node $v_{j}$ , travel along $e_{i j}$ and visit $v_{j}$ , then travel backwards along $e_{i j}$ . The sequence of labelled edges travelled along by beginning this process at $v_{0}$ is the depth-first walk of the tree. Note that each edge is visited exactly twice – once heading outwards, and again heading back towards the root.

This sequence can then be encoded as a Gödel number by the method in Section 1. We will define a function $ϕ (x, n)$ which takes an encoded tree $x$ and gives the parent of the vertex with label $n$ . Note that the root vertex’s label will not appear in this sequence because it has no associated edge.

Some functions to work with encoded trees:

To find the first and second occurrences of the edge with label $n$ in the walk:

$\begin{array}{rcl} f s t (x, n) & = & f i n d (x, n) \\ s n d (x, n) & = & f i n d (x [f s t (x, n) + 1 \dots l h (x)], n) \end{array}$

To get the label of the $n^{th}$ child of the root:

$\begin{array}{rcl} c h i l d (x, 0) & = & (x)_{0} \\ c h i l d (x, n + 1) & = & (x)_{s n d (x, c h i l d (x, n)) + 1} \end{array}$

To find the subtree descended from the $n^{th}$ child node:

$\begin{array}{rcl} s u b t r e e (x, n) & = & x [f s t (c h i l d (x, n)) + 1 \dots s n d (c h i l d (x, n)) - 1] \end{array}$

The number of children of the root node:

$n u m c h i l d r e n (x) = \underset{i < x}{μ} c h i l d (x, i) = 0$

Whether the root has a child with label $n$ :

$h a s c h i l d (x, n) = \underset{i < n u m c h i l d r e n (x)}{μ} c h i l d (x, i) = n$

Finally, the parent function. The idea is to basically do the depth-first walk, remembering which vertex you just came from. If you reach a subtree which doesn’t contain $n$ then turn back, or if you reach the required vertex then return the label of the vertex you just came from.

$\begin{array}{rcl} p_{x} (0) & = & 0 \\ p_{x} (n) & = & p a r e n t (x, n, 0) \\ p a r e n t (x, n, p) & = & {\begin{array}{lr} 0, & \neg (c o n t a i n s (x, n)), \\ p, & h a s c h i l d (x, n), \\ p a r e n t (s u b t r e e (x, z), n, c h i l d (x, z)), & otherwise. \end{array} \end{array}$

where $z := \underset{i < n u m c h i l d r e n (x)}{μ} c o n t a i n s (s u b t r e e (x, i), n)$ .

We will also need to know if the tree contains an edge $e_{i j}$ :

$h a s e d g e (x, i, j) \Leftrightarrow p_{x} (i) = j \land p_{x} (j) = i$

Theorem

A finite ordered tree is $E_{3}$ computable.

Proof

As the tree is finite, of course its labelling is $E_{3}$ -decidable, and $p_{b f x} (n)$ as defined above is $E_{3}$ -computable. $◻$