Revisions to Mapping between Notations

Defined the \operator math command

Source Link

edited Oct 31 at 5:20

6.4k
7
30
45

As$\DeclareMathOperator{\address}{address}$ As in my other question, it is assumed that the (total) function describing a given notation is denoted as $\operatorname{address}:p \rightarrow \Bbb{N}$$\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_{CK}$ (Church-Kleene). Denote the mapping from $N_1$ to $N_2$ as $P_{12}:\Bbb{N} \rightarrow \Bbb{N}$.

If we wanted to be more formal, we could say that consider the two functions $\operatorname{address1}:p\rightarrow \Bbb{N}$$\address1:p\rightarrow \Bbb{N}$ and $\operatorname{address2}:p\rightarrow \Bbb{N}$$\address2:p\rightarrow \Bbb{N}$ corresponding to $N_1$ and $N_2$ respectively. Then $P_{12}$ is defined by:

$$P_{12}(\operatorname{address1}(x))=\operatorname{address2}(x) \quad \text{for all} \quad x < p$$$$P_{12}(\address1(x))=\address2(x) \quad \text{for all} \quad 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_{12}$ 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.stackexchangethis same question on Math.com/questions/2380838/mapping-between-notationsSE). After no replies/comments since few days after posting it, I am posting it here. Hopefully that isn't a problem.

As in my other question, it is assumed that the (total) function describing a given notation is denoted as $\operatorname{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_{CK}$ (Church-Kleene). Denote the mapping from $N_1$ to $N_2$ as $P_{12}:\Bbb{N} \rightarrow \Bbb{N}$.

If we wanted to be more formal, we could say that consider the two functions $\operatorname{address1}:p\rightarrow \Bbb{N}$ and $\operatorname{address2}:p\rightarrow \Bbb{N}$ corresponding to $N_1$ and $N_2$ respectively. Then $P_{12}$ is defined by:

$$P_{12}(\operatorname{address1}(x))=\operatorname{address2}(x) \quad \text{for all} \quad 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_{12}$ 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.

$\DeclareMathOperator{\address}{address}$ 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_{CK}$ (Church-Kleene). Denote the mapping from $N_1$ to $N_2$ as $P_{12}:\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_{12}$ is defined by:

$$P_{12}(\address1(x))=\address2(x) \quad \text{for all} \quad 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_{12}$ 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 same question on Math.SE. After no replies/comments since few days after posting it, I am posting it here. Hopefully that isn't a problem.

Fonts for operators implemented

Source Link

edit approved Oct 31 at 5:20

Matemáticos Chibchas

215
5
14

As in my other question, it is assumed that the (total) function describing a given notation is denoted as $address:p\rightarrow \Bbb{N}$$\operatorname{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}$$p \in \omega_{CK}$ (Church-Kleene). Denote the mapping from $N_1$ to $N_2$ as $P{_1}{_2}:\Bbb{N} \rightarrow \Bbb{N}$$P_{12}:\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}$$\operatorname{address1}:p\rightarrow \Bbb{N}$ and $address2:p\rightarrow \Bbb{N}$$\operatorname{address2}:p\rightarrow \Bbb{N}$ corresponding to $N_1$ and $N_2$ respectively. Then $P{_1}{_2}$$P_{12}$ is defined by: $$P{_1}{_2}(address1(x))=address2(x) \qquad for \; all \; x < p$$

$$P_{12}(\operatorname{address1}(x))=\operatorname{address2}(x) \quad \text{for all} \quad 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}$$P_{12}$ 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.

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.

As in my other question, it is assumed that the (total) function describing a given notation is denoted as $\operatorname{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_{CK}$ (Church-Kleene). Denote the mapping from $N_1$ to $N_2$ as $P_{12}:\Bbb{N} \rightarrow \Bbb{N}$.

If we wanted to be more formal, we could say that consider the two functions $\operatorname{address1}:p\rightarrow \Bbb{N}$ and $\operatorname{address2}:p\rightarrow \Bbb{N}$ corresponding to $N_1$ and $N_2$ respectively. Then $P_{12}$ is defined by:

$$P_{12}(\operatorname{address1}(x))=\operatorname{address2}(x) \quad \text{for all} \quad 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_{12}$ 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.