Relationship between non-standard computation and TM(oracle)? We know that there are non-standard models of arithmetic, and in such models there are non-standard proofs of standardly unprovable sentences. Now, we can imagine a version of representability relative to some non-standard model of some arithmetical theory such that the said function would be what I would call a "non-standard computation". At the same time we can imagine the said computation otherwise correct, as in it would be the same as adding some real/oracle to a TM. Is there a nice way to connect these concepts? Is it a trivial connection? Can it give us insights about the base theory X or the sentence S such that X + "sentence S" $\vdash$ TM(oracle) halts?
 A: Let address the version of the question posed by Gro-Tsen in his
comments.

*

*Sets (a) and (c) are the same, and these are exactly the standard system of the model $M$, as mentioned in the answer of Patrick
Lutz. The standard system is equivalently defined as the set of traces on the standard
numbers of any sequence that is definable from parameters in $M$, whether or not
it is computable in $M$, since every (possibly nonstandard) finite initial
segment of a definable sequence is an element of $M$. Any sequence as in (a) or (c) will be the standard part of a definable
sequence in $M$ and thus in the standard system, and conversely,
any set in the standard system is the standard part of a pseudo
finite sequence in $M$, which can be hard-coded into a
(nonstandard) program $e$ in $M$, fulfilling (a) or (c).


*Set (b) consists of the sets of natural numbers that are the
trace of a set that is computably enumerable in $M$ by a standard
program $e$, such that this program gives output on all standard
input. This is equivalent to the sets of natural numbers such that
both it and its complement are the standard parts of sets that $M$ thinks are
computably enumerable using a standard program. In a model of true
arithmetic, this would be exactly the computably decidable sets,
since the operation of a standard program
$e$  would be the same in $\mathbb{N}$ as in $M$ in this case. Thus, this set can be strictly smaller than the sets in (a) and (c). Meanwhile, the universal
algorithm
(see also Arithmetic potentialism and the universal
algorithm
(arXiv:1801.04599) shows that
any given set of natural numbers can be placed into set (b) for a
suitable choice of $M$, since the universal algorithm $e$, which is
a standard program, can compute any set in a suitable model $M$ of
PA, and by arranging that the program enumerate the set in
increasing order, one will also be able to compute the complement
with a standard program. Nevertheless, set (b) is never equal to
the sets in (a) and (c), because the model $M$ can unify the
sets of (b) into a single subset of $\mathbb{N}\times\mathbb{N}$,
using program $e$ on slice $e$. This will be a set in the standard
system, from which all sets in (b) are computable, but the standard
system must have sets not computable from any given set.


*Set (d) consists of the standard parts of the sets that $M$
thinks are computably decidable by a standard program. In a model
of true arithmetic, these are exactly the computably decidable
sets, but by using the universal algorithm as above, we can place
any given set into set (d). The difference between set (d) and set
(b) is that the programs in (b) must halt only on all standard
input, but in (d) they must halt on all input. So set (d) is
contained in set (b). I would have to think harder whether the
sets can differ. But the argument I gave above shows that (d) is
never equal to (a) or (c).


*Sets (e) and (f) consists exactly of the finite sets of natural numbers.
Any finite set of natural numbers has the property in (e) and (f), and
conversely, if a set is infinite and definable in a nonstandard
model $M$ of PA, then it must have nonstandard elements, since
otherwise it would stand as a counterexample to induction in $M$.
A modified version of (e) would be the property (e'), asserting that $X\subset\mathbb{N}$ and there is some program $e\in M$ that halts on all input in $M$, such that $\forall i\in \mathbb{N} (i\in X\iff \{e\}(i)\downarrow=1)$.  This would be equivalent to (a) and (c).
A: Edit: I think the answers given so far do not completely address the original question nor Gro-Tsen's follow up questions. I believe I can address some of these points so I have greatly expanded my original answer. In brief, no reasonable notion of "computation according to a nonstandard model of arithmetic" seems to be equivalent to "standard computation with an oracle for some real." Additionally there is a pretty good characterization of which sets of Turing degrees can constitute the sets computable according to some nonstandard model of arithmetic.
Some terminology and standard results
Suppose $\mathcal{M}$ is a nonstandard model of arithmetic (meaning either PA or some weak fragment of PA containing a sufficient amount of induction to make all arguments below work).
First, some standard terminology. Pick some reasonable way of using natural numbers to code finite sequences and let $a(i)$ denote the $i^\text{th}$ element in the sequence coded by $a$. Define the standard system of $\mathcal{M}$, written $SSy(\mathcal{M})$, to be the set $$\{x \subseteq \mathbb{N} \mid \exists a\in M\, (\forall i \in \mathbb{N}\, (i \in x \iff a(i) = 1))\}.$$ In other words a subset of $\mathbb{N}$ is in the standard system of $\mathcal{M}$ if it is an initial segment of some $\mathcal{M}$-finite sequence coded by an element of $\mathcal{M}$.
If it is known that the standard system of any nonstandard model of PA has some special properties. First, it is closed under relative computability—i.e. if $x$ is in the standard system and $y \le_T x$ then $y$ is also in the standard system. Second, it is closed under computable joins—if $x$ and $y$ are both in the standard system then so is $x \oplus y$. Third, if $T$ is an infinite binary tree, some representation of which is in the standard system, then the standard system also contains some infinite path through $T$.
I believe these results are originally due to Dana Scott. A careful exposition of them can be found in Kaye's book on models of arithmetic. Unfortunately I don't have a copy of that book on hand so I can't provide a reference so instead I'll link to these notes by Tin Lok Wong (see Theorem 3.5 in particular).
Scott actually proved something more, which will be relevant below. Any set of reals which satisfies the three properties above is called a Scott set. The results mentioned above show that the standard system of any nonstandard model of PA is a Scott set. A partial converse is also true: Scott showed that any countable Scott set is the standard system of some model of PA and Knight and Nadel later extended this to Scott sets of size $\aleph_1$ (which finishes the story if we assume CH).
Lastly, let's note that no Scott set is equal to the set of reals computable from some oracle. To see why, let $A$ be a Scott set and suppose $A$ is equal to the reals computable from $x$. Then $x \in A$. But if we let $T$ be an infinite binary tree computable from $x$ with no infinite path computable from $x$ then we can see that $A$ must contain an infinite path through $T$ and thus not every real in $A$ is computable from $x$.
Computation According to a Nonstandard Model
Let $\mathcal{M}$ be a nonstandard model of arithmetic and define "computation according to $\mathcal{M}$ as follows: say that a set $x \subseteq \mathbb{N}$ is "computable according to $\mathcal{M}$ if there is some (possibly nonstandard) number $e \in M$ such that $\mathcal{M} \models \forall n\, (\varphi_e(n) \downarrow)$ and $x = \{n \in \mathbb{N} \mid \mathcal{M} \models \varphi_e(n) = 1\}$—in other words, $\mathcal{M}$ believes that the program coded by $e$ converges on every input and $x$ consists of those natural numbers on which $\mathcal{M}$ believes that $e$ converges and is equal to $1$.
It is easy to see that every set in $SSy(\mathcal{M})$ is also "computable according to $\mathcal{M}$." The converse is also true. Indeed, it is provable in PA that for any index for a program $e$ and any number $b$, there is a number $a$ coding a sequence which records those numbers less than $b$ on which the program coded by $e$ converges and outputs $1$ (i.e. $a$ codes a sequence of length $b$ and $a(i) = 1$ if and only if $i < b$ and $\varphi_e(i) = 1$). Now suppose $e$ is a (possibly nonstandard) index for a program. Let $b$ be any nonstandard number and let $a$ be a nonstandard number coding the sequence we have just mentioned. Then the set $\{i \in \mathbb{N} \mid a(i) = 1\}$ is exactly the subset of $\mathbb{N}$ "computed by $e$ according to $\mathcal{M}$" and it is clearly in the standard system of $\mathcal{M}$.
Since the set of reals "computable according to $\mathcal{M}$" is exactly $SSy(\mathcal{M})$ and $\mathcal{M}$ is a Scott set, the set of reals "computable according to $\mathcal{M}$" cannot be equal to the set of reals computable from some oracle.
What if the program only needs to converge on every natural number?
Gro-Tsen proposed a number of modifications of the above definition of "computation according to $\mathcal{M}$." The first modification is to relax the requirement on what it means for a program to converge on all inputs. Above we required that $\mathcal{M}$ believes that the program coded by $e$ converges on all inputs in $\mathcal{M}$. What if we only require that $\mathcal{M}$ believes it converges on all inputs in $\mathbb{N}$? In other words instead of $\mathcal{M} \models \forall n\, (\varphi_e(n) \downarrow)$ we only require $\forall n \in \mathbb{N}\,(\mathcal{M} \models \varphi_e(n)\downarrow)$?
The answer is that this doesn't change anything. In particular, suppose $e$ is an element of $\mathcal{M}$ which codes a program which $\mathcal{M}$ believes converges on every input in $\mathbb{N}$. By overspill there must be some nonstandard number $b$ such $\mathcal{M}$ believes that the program coded by $e$ converges on all inputs less than $b$. Let $e'$ be an index for a program which does the same thing as $e$ on all inputs less than $b$ and immediately halts and outputs $0$ on any input greater than $b$. Then the program coded by $e'$ converges on every input in $\mathcal{M}$ and corresponds to the same subset of $\mathbb{N}$ as $e$.
What if the program index has to be a (standard) natural number?
The next modification proposed by Gro-Tsen is more serious. What if we require that the index $e$ be a standard natural number rather than an arbitrary element of $\mathcal{M}$? The answer is that with this new requirement, the sets "computable according to $\mathcal{M}$ still cannot coincide with the sets computable from some oracle, except in one very special case.
To explain things more clearly, let me make another definition. Let's define the computable standard system of $\mathcal{M}$, written $CSSy(\mathcal{M})$, to be the set $$\{x \subseteq \mathbb{N} \mid \exists e \in \mathbb{N} \, \forall n \in \mathbb{N} \, (\mathcal{M} \models \varphi_e(n)\downarrow \text{ and } (n \in x \iff \mathcal{M} \models \varphi_e(n) = 1)\}$$ (note that this is not standard terminology). As Joel David Hamkins pointed out in his answer, $CSSy(\mathcal{M})$ can never be equal to $SSy(\mathcal{M})$ for any nonstandard model. The question is then: when is $CSSy(\mathcal{M})$ equal to the set of reals computable from some oracle?
The answer is that this can only occur if $CSSy(\mathcal{M})$ is exactly the set of computable reals. However, unlike the situation above, this can occur even if $\mathcal{M}$ is nonstandard.
For example, suppose $\mathcal{M}$ is a model of the true first order theory of the natural numbers. Then for any $e\in \mathbb{N}$, the program coded by $e$ will have the same behavior in $\mathcal{M}$ as it does in the "real world" so $CSSy(\mathcal{M})$ will not contain any noncomputable reals. And by compactness, it is possible for $\mathcal{M}$ to be nonstandard.
However, if $CSSy(\mathcal{M})$ contains any noncomputable real then it must actually be a Scott set and thus cannot be equal to the set of reals computable from some oracle. The only difficult part of this is to show that $CSSy(\mathcal{M})$ is closed under finding infinite paths through infinite binary trees so here's a proof of that part.
First, suppose $e \in \mathbb{N}$ is an index for a program and $n \in \mathbb{N}$ is an input such that $\varphi_e(n)$ diverges but $\mathcal{M}$ believes it converges (such an $e$ and $n$ must exist if $CSSy(\mathcal{M})$ contains any noncomputable sets). Let $T$ be an infinite binary tree which is in $CSSy(\mathcal{M})$. Let $a$ be the program which does the following on input $i$: first, it waits for $\varphi_e(n)$ to converge. If it converges after $m$ steps then $a$ looks for the largest $k \leq m$ such that $T$ contains a path of length $k$. If $i \leq k$ then it prints the $i^\text{th}$ element of the leftmost path of length $k$ in $T$. Otherwise it prints $0$. By overspill, $\mathcal{M}$ believes $T$ contains a path of nonstandard length so in $\mathcal{M}$ the program coded by $a$ will print a valid path through ($\mathcal{M}$'s version of) $T$ and when restricted to $\mathbb{N}$ that is an honest infinite path through $T$. However, since the description we gave above of $a$ only depended on the standard numbers $e$ and $n$, $a$ is itself standard and thus this infinite path is in $CSSy(\mathcal{M})$.
What if we require the program to converge on all inputs in $\mathcal{M}$?
In the definition of $CSSy(\mathcal{M})$ above, I only required the program $e$ to converge on all inputs in $\mathbb{N}$, not all inputs in $\mathcal{M}$. What if we change this? It turns out this doesn't really change anything about the above proof (basically because we were able to ensure that $a$ converges on all inputs) and so in this new version, $CSSy(\mathcal{M})$ is still either the set of computable reals or a Scott set (though perhaps a different Scott set than under the old definition).
What if we don't intersect with $\mathbb{N}$ in the definitions above?
It might seem a bit funny that when we looked at sets "computed according to $\mathcal{M}$ we were always taking an intersection with $\mathbb{N}$—i.e. we looked at $\{n \in \mathbb{N} \mid \varphi_e(n) = 1\}$ rather than $\{n \in M \mid \varphi_e(n) = 1\}$. This is for good reason. As mentioned by Joel David Hamkins, overspill implies that any set of the latter form is either finite or contains nonstandard numbers. So if we are ultimately interested in sets of natural numbers then this version of the question is very boring (the only sets of natural numbers "computable according to $\mathcal{M}$" are finite sets).
What are the sets of Turing degrees in each of these scenarios?
Gro-Tsen also asked about the possible sets of Turing degrees corresponding to each definition of "computable according to $\mathcal{M}$." Here, there is a pretty good partial answer. For each non-trivial definition above, the reals "computable according to $\mathcal{M}$" must always comprise a Scott set (though the converse is not clear). And quite a lot is known about sets of Turing degrees which form a Scott set so quite a lot is known about sets of Turing degrees which are those "computable according to $\mathcal{M}$" for some nonstandard $\mathcal{M}$.
