An ordinal $\alpha$ is said to be computable if there is a computable relation on a subset of integers that is well-ordered and its order type equals $\alpha$.

But let's consider well-founded trees on $\Bbb N$. Such a tree $T$ is a set of finite sequences $(x_1,\dots,x_n)$ of $\Bbb N$ closed under taking initial segments and such that there is no infinite sequence $(x_i)_{i<\omega}$ for which $(x_1,\dots,x_n) \in T$ for any $n$.

There is a natural way to assign an ordinal rank for nodes in such trees (rank of a node is 1 plus the supremum of ranks of its children). For any countable ordinal $\alpha$ we can construct a tree with the root having ordinal rank $\alpha$.

Sure, we can view a tree as a relation on the set of its nodes. And say that a tree is computable if the corresponding relation is computable.

But there is another way to define computable well-founded trees — recursively. We can say that

- the trivial tree with the single root node is computable
- a tree is computable if all subtrees of its root node are computable and there is a computable enumeration of them

It's not hard to come up with a concrete notation for such computable trees.

Since trees have ordinal ranks it gives us an alternative definition of computable ordinals.

I wonder if this definition is actually the same as the common one. And if not what are the implications? Can we compare their supremum with the Church-Kleene ordinal?

As an encoding of trees I'm thinking of programs (in some Turing complete language) that produce sequences of numbers $n$, where each $n$ is the encoding of a program that produces a subtree. As a special case, $0$ encodes the trivial tree directly. The encoding of programs by numbers is computable.

1more comment