This is similar sounding to a question I asked quite recently on MO. However, the question asks something different. Hopefully someone will answer the question.
It is assumed that the (total) function describing a given notation is denoted as $address:p\rightarrow N$ and assumed to be bijective.
Suppose we are given two notations $N1$ and $N2$ for some $p \in \omega{_C}{_K}$(Church-Kleene). Denote the mapping from $N1$ to $N2$ as $P{_1}{_2}:N \rightarrow N$.
If we wanted to be more formal, we could say that consider the two functions $address1:p\rightarrow N$ and $address2:p\rightarrow N$ corresponding to $N1$ and $N2$ 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 $N1$ and $N2$ are computable. My question simply is the following: Is the function $P{_1}{_2}$ always equivalence-computable (computable using a program that has access to oracle deciding equivalence of ordinary programs)? 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 proof(if there is one) for a reasonable upper-bound(or lack of it) is provided.
Edit: modified the question slightly