Are well-orders of the same recursive length recursively isomorphic?

Question

If the ordinal length of $A$ and $B$ is the same recursive ordinal, does it follow that there is a recursive one-one order-preserving correspondence between $A$ and $B$?

Answer 1

Consider an acceptable programming system $(\phi_n)$.

Consider $f$ from $\mathbb N$ to $\mathbb N$ such that :

1. if $\phi_n(n)$ halts then $f(n)=2\times\left|\{i\le n\;|\;\phi_i(i)\mbox{ halts}\}\right|$
2. if $\phi_n(n)$ nevers halts then $f(n)=1+2\times\left|\{i\le n\;|\;\phi_i(i)\mbox{ never halts}\}\right|$

Hence $f$ is a bijection.

Let $A$ be $\mathbb N$ with the usual order, so $A$ is a set of order length $\omega$ ($\omega$ is recursive).

Let $B$ be $\mathbb N$ with the special order $x\le_B y$ iff $f(x)\le_A f(y)$, so $B$ is also a set of order length $\omega$.

But $f$ is the order preserving bijection from $B$ to $A$ and $f$ is not recursive.