If two models of set theory $U$ and $W$ have the same arithmetic structure $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, then as you observe the operation of Turing machines will be absolute between $U$ and $W$, and so they will think precisely the same sets are decidable. Furthermore, they will agree on the members of any arithmetic set defined by a standard-length formula $\varphi$.

Things get very interesting, however, if one considers the possibly nonstandard-length arithmetic formulas from inside the models, and in this case it is not correct to say that $U$ and $W$ must agree on all sets that they think are arithmetic. For example, in my paper, Satisfaction is not absolute, joint with Ruizhi Yang, we prove a number of instances of such models of set theory disagreeing on what they think is arithmetic truth.

One interesting example there occurs when two models $U$ and $W$ of ZFC have the same natural numbers $\mathbb{N}^U=\mathbb{N}^W$ and the same arithmetic structure, and have a Turing machine program $e$ that computes a relation $\lhd$ on $\mathbb{N}$, which both $U$ and $W$ think is a linear order on $\mathbb{N}$, but $U$ thinks it is well ordered and $W$ thinks it is not well ordered. So the two models agree on all Turing machine computations, but they disagree on the computable ordinals and on $\omega_1^{CK}$.

Another interesting example occurs with the construction of two models of set theory $U$ and $W$ which agree on the arithmetic structure $\mathbb{N}^U=\mathbb{N}^W$, and have a subset $A\subset \mathbb{N}$ in common, such that $U$ thinks $A$ is arithmetic, but $W$ does not. There are many more similar such strange examples in the paper.

Meanwhile, the answer to your question at the end is affirmative.

Theorem. If $M$ is any countable model of PA, and $A\subset M$ is a set such that $\langle M,+,\cdot,A\rangle\models\text{PA}^*$, meaning that it satisfies induction in the expanded language, then there is an elementary end-extension $M\prec N$ such that $A$ is coded in $N$, in the sense that there is some $a\in N$ such that $i\in A$ if and only if $N$ thinks that the $i^{th}$ prime $p_i$ divides $a$ in $N$.

Thus, even though the set $A$ might not be computable in $M$, it becomes the initial segment of a computable set in $N$. For example, the halting problem of $M$ or indeed any definable subset of $M$ becomes the initial segment of a computable and indeed pseudo-finite set in $N$.

The theorem can be proved by means of a definable ultrapower of $\langle M,+,\cdot,A\rangle$. One defines the $M$-ultrafilter $U$ in $\omega$ many steps so that every function $f:M\to M$ that is definable in that structure and bounded by an element of $M$ is constant on a set in $U$. It follows that the ultrapower $N$, using all definable functions in $\langle M,+\cdot,A\langle$, is an elementary top-extension, and $A$ will be coded since we may define the function coding longer and longer pieces of $A$.

We can also arrange that these models arise as the $\mathbb{N}$ of models of ZFC.

If two models of set theory $U$ and $W$ have the same arithmetic structure $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, then as you observe the operation of Turing machines will be absolute between $U$ and $W$, and so they will think precisely the same sets are decidable. Furthermore, they will agree on the members of any arithmetic set defined by a standard-length formula $\varphi$.

Things get very interesting, however, if one considers the possibly nonstandard-length arithmetic formulas from inside the models, and in this case it is not correct to say that $U$ and $W$ must agree on all sets that they think are arithmetic. For example, in my paper, Satisfaction is not absolute, joint with Ruizhi Yang, we prove a number of instances of such models of set theory disagreeing on what they think is arithmetic truth.

One interesting example there occurs when two models $U$ and $W$ of ZFC have the same natural numbers $\mathbb{N}^U=\mathbb{N}^W$ and the same arithmetic structure, and have a Turing machine program $e$ that computes a relation $\lhd$ on $\mathbb{N}$, which both $U$ and $W$ think is a linear order on $\mathbb{N}$, but $U$ thinks it is well ordered and $W$ thinks it is not well ordered. So the two models agree on all Turing machine computations, but they disagree on the computable ordinals and on $\omega_1^{CK}$.

Another interesting example occurs with the construction of two models of set theory $U$ and $W$ which agree on the arithmetic structure $\mathbb{N}^U=\mathbb{N}^W$, and have a subset $A\subset \mathbb{N}$ in common, such that $U$ thinks $A$ is arithmetic, but $W$ does not. There are many more similar such strange examples in the paper.

Meanwhile, the answer to your question at the end is affirmative.

Theorem. If $M$ is any countable model of PA, and $A\subset M$ is a set such that $\langle M,+,\cdot,A\rangle\models\text{PA}^*$, meaning that it satisfies induction in the expanded language, then there is an elementary end-extension $M\prec N$ such that $A$ is coded in $N$, in the sense that there is some $a\in N$ such that $i\in A$ if and only if $i\in M$ and $N$ thinks that the $i^{th}$ prime $p_i$ divides $a$ in $N$.

Thus, even though the set $A$ might not be computable in $M$, it becomes the initial segment of a computable set in $N$. For example, the halting problem of $M$ or indeed any definable subset of $M$ becomes the initial segment of a computable and indeed pseudo-finite set in $N$.

The theorem can be proved by means of a definable ultrapower of $\langle M,+,\cdot,A\rangle$. One defines the $M$-ultrafilter $U$ either generically, or in $\omega$ many steps so that every function $f:M\to M$ that is definable in that structure and bounded by an element of $M$ is constant on a set in $U$. It follows that the ultrapower $N$, using all definable functions in $\langle M,+\cdot,A\rangle$, is an elementary top-extension, and $A$ will be coded since we may define the function coding longer and longer pieces of $A$.

We can also arrange that these models arise as the $\mathbb{N}$ of models of ZFC.

If two models of set theory $U$ and $W$ have the same arithmetic structure $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, then as you observe the operation of Turing machines will be absolute between $U$ and $W$, and so they will think precisely the same sets are decidable. Furthermore, they will agree on the members of any arithmetic set defined by a standard-length formula $\varphi$.

Things get very interesting, however, if one considers the possibly nonstandard-length arithmetic formulas from inside the models, and in this case it is not correct to say that $U$ and $W$ must agree on all sets that they think are arithmetic. For example, in my paper, Satisfaction is not absolute, joint with Ruizhi Yang, we prove a number of instances of such models of set theory disagreeing on what they think is arithmetic truth.

One interesting example there occurs when two models $U$ and $W$ of ZFC have the same natural numbers $\mathbb{N}^U=\mathbb{N}^W$ and the same arithmetic structure, and have a Turing machine program $e$ that computes a relation $\lhd$ on $\mathbb{N}$, which both $U$ and $W$ think is a linear order on $\mathbb{N}$, but $U$ thinks it is well ordered and $W$ thinks it is not well ordered. So the two models agree on all Turing machine computations, but they disagree on the computable ordinals and on $\omega_1^{CK}$.

Meanwhile, the answer to your question at the end is affirmative.

Theorem. If $M$ is any countable model of PA, and $A\subset M$ is a set such that $\langle M,+,\cdot,A\rangle\models\text{PA}^*$, meaning that it satisfies induction in the expanded language, then there is an elementary end-extension $M\prec N$ such that $A$ is coded in $N$, in the sense that there is some $a\in N$ such that $i\in A$ if and only if the $i^{th}$ prime $p_i$ divides $a$ in $N$.

Thus, even though the set $A$ might not be computable in $M$, it becomes the initial segment of a computable set in $N$.

The theorem can be proved by means of a definable ultrapower of $\langle M,+,\cdot,A\rangle$. One defines the $M$-ultrafilter $U$ in $\omega$ many steps so that every function $f:M\to M$ that is definable in that structure and bounded by an element of $M$ is constant on a set in $U$. It follows that the ultrapower $N$, using all definable functions in $\langle M,+\cdot,A\langle$, is an elementary top-extension, and $A$ will be coded since we may define the function coding longer and longer pieces of $A$.

We can also arrange that these models arise as the $\mathbb{N}$ of models of ZFC.

If two models of set theory $U$ and $W$ have the same arithmetic structure $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, then as you observe the operation of Turing machines will be absolute between $U$ and $W$, and so they will think precisely the same sets are decidable. Furthermore, they will agree on the members of any arithmetic set defined by a standard-length formula $\varphi$.

Things get very interesting, however, if one considers the possibly nonstandard-length arithmetic formulas from inside the models, and in this case it is not correct to say that $U$ and $W$ must agree on all sets that they think are arithmetic. For example, in my paper, Satisfaction is not absolute, joint with Ruizhi Yang, we prove a number of instances of such models of set theory disagreeing on what they think is arithmetic truth.

One interesting example there occurs when two models $U$ and $W$ of ZFC have the same natural numbers $\mathbb{N}^U=\mathbb{N}^W$ and the same arithmetic structure, and have a Turing machine program $e$ that computes a relation $\lhd$ on $\mathbb{N}$, which both $U$ and $W$ think is a linear order on $\mathbb{N}$, but $U$ thinks it is well ordered and $W$ thinks it is not well ordered. So the two models agree on all Turing machine computations, but they disagree on the computable ordinals and on $\omega_1^{CK}$.

Another interesting example occurs with the construction of two models of set theory $U$ and $W$ which agree on the arithmetic structure $\mathbb{N}^U=\mathbb{N}^W$, and have a subset $A\subset \mathbb{N}$ in common, such that $U$ thinks $A$ is arithmetic, but $W$ does not. There are many more similar such strange examples in the paper.

Meanwhile, the answer to your question at the end is affirmative.

Theorem. If $M$ is any countable model of PA, and $A\subset M$ is a set such that $\langle M,+,\cdot,A\rangle\models\text{PA}^*$, meaning that it satisfies induction in the expanded language, then there is an elementary end-extension $M\prec N$ such that $A$ is coded in $N$, in the sense that there is some $a\in N$ such that $i\in A$ if and only if $N$ thinks that the $i^{th}$ prime $p_i$ divides $a$ in $N$.

Thus, even though the set $A$ might not be computable in $M$, it becomes the initial segment of a computable set in $N$. For example, the halting problem of $M$ or indeed any definable subset of $M$ becomes the initial segment of a computable and indeed pseudo-finite set in $N$.

The theorem can be proved by means of a definable ultrapower of $\langle M,+,\cdot,A\rangle$. One defines the $M$-ultrafilter $U$ in $\omega$ many steps so that every function $f:M\to M$ that is definable in that structure and bounded by an element of $M$ is constant on a set in $U$. It follows that the ultrapower $N$, using all definable functions in $\langle M,+\cdot,A\langle$, is an elementary top-extension, and $A$ will be coded since we may define the function coding longer and longer pieces of $A$.

We can also arrange that these models arise as the $\mathbb{N}$ of models of ZFC.