Suppose we have two models of set theory, $U$ and $V$ which have the same $\Bbb N$. Is it possible that there is a set $A\subseteq\Bbb N$ such that, in $U$, this set is computable, i.e. there is a number $e\in\Bbb N$ which is index of Turing machine recognizing $A$, but it doesn't hold in $V$? I believe answer to this question is "no", because it looks like TM computations are absolute between models with same natural numbers.


What will happen if we drop the requirement of them having the same $\Bbb N$? Can there be a set then, which is subset of both $\Bbb N^U$ and $\Bbb N^V$, and is computable in one universe but not another? Here there are wider possibilities, because we can have index $e$ which exists on one model and not another, and we can also have "longer" computations (i.e. amount of steps which exists in one model but not another).


Last, related, question, is about extending the models: suppose we have a model $V$ in which set $A\subseteq\Bbb N$ is uncomputable. Is it always the case that we can extend this model (e.g. add more natural numbers in some way) so that $A$ will become computable? One counterexample would be, say, $0'$, but it could also become computable, because there will be more indices of TMs, and $0'$ would cover only the old ones.


I tried to explain the above as clearly as I could. Thanks for all the feedback.



Are there sets which are computable in one model, but uncomputable in another?
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](http://jdh.hamkins.org/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.


