Tetration and higher-order operations on transfinite ordinals

[quickfur]

[...]
Just skimmed through your article and asking myself how this function can be expressed with a recursive definition ...

I've not thought about that... but I assume it must be possible since the algorithm obviously can be expressed as a Turing machine, so it must be recursive. I'm not sure how exactly to go about deriving a recursive definition for it, though.

Maybe one way is to perform a depth-first traversal on the tree, left child first, and recursively linearize the left-most children. So, in computer pseudocode, it could be something like this:

Code:

linearize(T,m) {
    if (is_rightbranching_chain(T.left_subtree) and
        is_rightbranching_chain(T.right_subtree))
    {
        ... (perform the transformation... not sure how to express this recursively yet)
    } else {
        T.left_subtree = linearize(T.left_subtree, m);
        T.right_subtree = linearize(T.right_subtree, m);
        return T;
    }
}

Once we work out the pseudocode, maybe there's a way to factor it into a recursive function...?