As in my other question, it is assumed that the (total) function describing a given notation is denoted as $address:p\rightarrow \Bbb{N}$ and assumed to be bijective. 


Suppose we are given two notations $N\_1$ and $N\_2$ for some $p \in \omega{\_C}{\_K}$(Church-Kleene). Denote the mapping from $N\_1$ to $N\_2$ as $P{\_1}{\_2}:\Bbb{N} \rightarrow \Bbb{N}$.


If we wanted to be more formal, we could say that consider the two functions $address1:p\rightarrow \Bbb{N}$ and $address2:p\rightarrow \Bbb{N}$ corresponding to $N\_1$ and $N\_2$ respectively. Then $P{\_1}{\_2}$ is defined by:
$$P{\_1}{\_2}(address1(x))=address2(x) \qquad for \; all \; x < p$$


Now assume that the less-than relations corresponding to $N\_1$ and $N\_2$ are computable. My question simply is the following: Is the function $P{\_1}{\_2}$ always Total-computable? That is, computable using an oracle-program that has access to the set representing "indexes of total recursive functions". 


If no, then what would be the example for it (also generally, what would be the suitable upper-bound in that case). If yes, then can someone give a reference where a complete or partial proof(if there is one) for a reasonable upper-bound(or lack of it) is provided.


P.S.
I posted this question on Math.SE (<https://math.stackexchange.com/questions/2380838/mapping-between-notations>). After no replies/comments since few days after posting it, I am posting it here. Hopefully that isn't a problem. 



Mapping between Notations
Your question is about the oracle strength needed to compute an
isomorphism between two isomorphic computable well-orders. In
general, $0''$ is not necessarily enough to compute such an isomorphism, unless the order-types are sufficiently small, and the general
phenomenon is that the strength needed to compute the isomorphisms rises with the length of the order types being considered.


Let's begin by pointing out what various oracles can compute about a computable well-order relation.


**Theorem.** Suppose that $\langle\mathbb{N},\lhd\rangle$ is a
computable well-order relation.


1. Oracle $0'$ can compute the adjacency relation.
2. Oracle $0''$ can identify limit ordinal nodes.
3. Oracle $0'''$ can compute the "next limit" relation, i.e. where $a\lhd b$ and $b$ is a limit, with no limits between.
4. Oracle $0''''$ can identify limits-of-limits.
5. Oracle $0^{(5)}$ can compute the next-limit-of-limits.


**Proof.** Given $a\lhd b$, the oracle $0'$ can tell if we'll ever
find $c$ such that $a\lhd c\lhd b$ and thereby know whether or not
$a$ and $b$ are adjacent.


Node $b$ is a limit ordinal node, if every $a\lhd b$ does have such
a $c$ between, and this is a $\Pi\_2$ question to which $0''$ knows
the answer. So oracle $0''$ can identify the limit ordinal nodes.


Similarly, $b$ is the next limit after $a$, if $a\lhd b$ and every
$c$ between them has a predecessor, which is a $\Pi\_3$ question
that $0'''$ can answer. So $0'''$ can compute the next-limit
relation.


A node $b$ is a limit-of-limits, if every smaller node has another
limit node between. This is a $\pi\_4$ assertion that $0''''$ can
answer.


And so on. $\Box$


We can use this to find upper bounds on the strength needed to compute
isomorphisms for various small order-types.


**Corollary.**


1. For any two computable well-orders of the same order-type less
than $\omega^2$, oracle $0'$ can compute the isomorphism.
2. For any two computable well-orders of the same order-type less
than $\omega^3$, oracle $0'''$ can compute the isomorphism.
3. For any two computable well-orders of the same order-type less
than $\omega^4$, oracle $0^{(5)}$ can compute the isomorphism.


**Proof.** If the orders have type less than $\omega^2$, then they
have only finitely many limit ordinal nodes, which can be
hard-coded into the program. And then the rest of the isomorphism
amounts to finding adjacencies, which can be computed from $0'$.


If the orders have type less than $\omega^3$, then they have at
most finitely many limits-of-limits, which can be hard-coded into
the program. And the rest of the isomorphism amounts to finding the
next-limit and the corresponding adjacencies, which can be computed
from $0'''$.


And so on. $\Box$


Meanwhile, we can show that for certain small order-types, one does in fact need strength. 


**Theorem.**
 There are two computable order relations on $\mathbb{N}$ of order type $\omega$, with no
 computable isomorphism.


**Proof.** Let the first order be the natural numbers with the
usual ordering $\langle\mathbb{N},<\rangle$, which has order type
$\omega$. Let the second order be constructed in the following
computable manner. Put the Turing machines in order in type
$\omega$ and for each machine $p$, create two points $a\_p$ and
$b\_p$ and specify $a\_p<b\_p$. Now, begin simulating all programs,
and whenever a new program halts, add a new point $c\_p$ with
$a\_p<c\_p<b\_p$. This specifies a computable order with order type
$\omega$. But there can be no computable isomorphism between this
order and the first order, because if there were, we could
computably determine whether or not $b\_p$ was a successor of $a\_p$
or not, and thereby computable solve the halting problem, which is
impossible. $\Box$


**Theorem.** There are two computable relations with order-type
$\omega^2$, having no $0'$-computable isomorphism relation.


**Proof.** Let the first order of type $\omega^2$ be a computable
ordering for which the map $(n,k)\mapsto\omega\cdot n+k$ is
computable. We build the second order by the following computable
procedure. Order the Turing machines $p$ in order type $\omega$.
Create an interval in our new order associated with each $p$. The
interval will either be finite or infinite (but infinitely many of
them will be infinite, and so the order overall will have type
$\omega^2$). We simulate all programs on input $0$, input $1$,
input $2$ and so on. Every time a program halts on the next input,
we add another point to its interval block. Thus, the total
programs will lead to infinite intervals, but the non-total
programs will lead to finite intervals, since they will be waiting
for their next input to halt. There can be no $0'$-computable
isomorphism from the first order to the second, since from any such
isomorphism, we could tell whether or not an interval was infinite
or not, and thereby come to solve the $\Pi\_2$-complete problem of
totality, which is not possible using only $0'$ as an oracle.
$\Box$


**Theorem.** There are two computable relations with order-type
$\omega^3$, having no $0''$-computable isomorphism relation.


**Proof.** For the first order, we can use a standard ordinal
denotation for which the function $(n,m,k)\mapsto
\omega^2\cdot n+\omega\cdot m+k$ is computable. We build the second order by
the following computable procedure. Consider any complete
$\Sigma\_3$ relation $A(w)\iff
\exists x\forall y\exists z\ R(w,x,y,z)$, where $R$ is $\Delta\_0$.
We may assume that infinitely many $w$ have such an $x$, that every
$(w,x)$ has infinitely many $y$ with some $z$ for which
$R(w,x,y,z)$, and that when there is an $x$ for $w$, then there are
infinitely many such $x$. For each $(w,x)$, we create a node in the
lexical order, and then we begin inspecting the various $y$ in
turn, searching for a $z$ for which $R(w,x,y,z)$ (but waiting for
each $y$ to finish before considering the next). Every time we find
that $(w,x)$ admits the next $y$ having such a $z$, then we add
another node to the interval associated with $(w,x)$. Thus, this
$x$ will be an acceptable witness for $w$ if this interval grows
infinitely often, and otherwise it will have only finitely many
points. So $w$ will satisfy the property $\exists x\forall y\exists
z\ R(w,x,y,z)$ if and only if the interval associated with $w$
(ranging over all possible $x$) has order type strictly exceeding
$\omega$, and otherwise it will have order type $\omega$. It
follows from our assumptions on the relation $R$ that this relation
has order type $\omega^3$. But finally, any isomorphism of this
relation to the standard notations for ordinals below $\omega^3$
will tell us the length of the interval associated with $w$. So if
$0''$ could compute the isomorphism, then it could solve the
$\Sigma\_3$ relation with which we began, and this is impossible.
Since that relation was $\Sigma\_3$-complete, there can be no such
isomorphism computable from $0''$. $\Box$


I believe that these methods can be pushed harder, and one might
expect to prove the optimal results. 


