Return to Answer

Proof. If the graph of $f$ is $\Sigma^0_2$, then $f$ is computable from $0'$. Since in any nonstandard model of true arithmetic, we can from any nonstandard number compute an approximation to $0'$ by simultating for $H$ steps, and this will be correct on the standard part. We can therefore use that oracle we generated to compute $f$, and since $f$ is total, we will never need to reach into the nonstandard part of the oracle for any standard input. So $f$ will be computable with true nonstandard help.

Conversely, suppose that $f$ is a total function and computable with true nonstandard help by program $p$. It follows that $p$ on input $(n,H)$ gives output $f(n)$ with any nonstandard model of true arithmetic and any nonstandard $H$. Since any larger $H$ would also work, it follows that $p$ with input $(n,k)$ must give output $f(n)$ for all sufficiently large $k$, including sufficiently large standard $k$. In other words, $f(n)=m$ just in case there is $K$ such that for all $k\geq K$ program $p$ on input $(n,k)$ gives output $m$. This is a $\Sigma^0_2$-definable property, and so the theorem is proved. $\Box$

This theorem seems to answer the question concerning the exact complexity of having a nonstandard but arbitrary nonstandard auxiliary input.

Proof. If the graph of $f$ is $\Sigma^0_2$, then $f$ is computable from $0'$. Since in any nonstandard model of true arithmetic, we can from any nonstandard number compute an approximation to $0'$ by simulating for $H$ steps, and this will be correct on the standard part. We can therefore use that oracle we generated to compute $f$, and since $f$ is total, we will never need to reach into the nonstandard part of the oracle for any standard input. So $f$ will be computable with true nonstandard help.

Conversely, suppose that $f$ is a total function and computable with true nonstandard help by program $p$. It follows that $p$ on input $(n,H)$ gives output $f(n)$ with any nonstandard model of true arithmetic and any nonstandard $H$. Since any larger $H$ would also work, it follows that $p$ with input $(n,k)$ must give output $f(n)$ for all sufficiently large $k$, including sufficiently large standard $k$. It follows that $f(n)=m$ just in case there is $K$ such that for all $k\geq K$ and all halting computations of program $p$ on input $(n,k)$ gives output $m$. This is a $\Sigma^0_2$-expressible property, and so the theorem is proved. $\Box$

Let me interpret your question like this, which seems to accord with your idea of running a Turing machine computation inside a nonstandad model of arithmetic with an arbitrary nonstandard element.

Specifically, let us say that a Turing machine program $p$ computes a function $f$ on the natural numbers with nonstandard help, if for any $a\in\mathbb{N}$ and any nonstandard $N\models\text{PA}$ and any nonstandard number $H\in N$, if we run $p$ inside $N$ with input $(n,H)$, then the program halts and gives output $f(n)$, if $n$ is in the domain of $f$, and otherwise it does not halt in $N$.

Update. I've realized now that one may achieve a better interpretation by considering only models of true arithmetic. In this case, the notion will be much more powerful.

One can now easily see that $0'$ and $0''$ and so on are computable with true nonstandard help. By iterating this, we can see that any arithmetically definable function is computable with true nonstandard help, and one can transcend this by uniformly computing the jumps. So $0^{+\omega}$ is computable with true nonstandard help, and thus true arithmetic itself is computable with true nonstandard help. And then one can iterate further, climbing into the hyperarithmetic hiearchy.

I shall give two different interpretations of the question. (The second interpretation using true arithmetic is modified in this update.)

Using arbitrary nonstandard models of PA. Let us say that a Turing machine program $p$ computes a function $f$ on the natural numbers with nonstandard help, if for any $a\in\mathbb{N}$ and any nonstandard $N\models\text{PA}$ and any nonstandard number $H\in N$, if we run $p$ inside $N$ with input $(n,H)$, then the program halts and gives output $f(n)$, if $n$ is in the domain of $f$, and otherwise it does not halt in $N$.

Using only nonstandard models of true arithmetic. A better interpretation is obtained by considering only models of true arithmetic, which I think is closer to what you may have meant by referring to nonstandard analysis.

One can easily see that $0'$ is computable with true nonstandard help, since one can simulate any Turing machine program for $H$ steps inside any model of true arithmetic, and this will get the right answer for standard input, precisely because the model is a model of true arithmetic. At first, I had thought that we could use that nonstandard fake version of $0'$ and do the same thing to compute $0''$ and $0'''$ and more, but I now think this is wrong. Rather, what is going on is the following:

Theorem. A total function on $\mathbb{N}$ is computable with true nonstandard help if and only if the graph of $f$ has complexity $\Sigma^0_2$.

Proof. If the graph of $f$ is $\Sigma^0_2$, then $f$ is computable from $0'$. Since in any nonstandard model of true arithmetic, we can from any nonstandard number compute an approximation to $0'$ by simultating for $H$ steps, and this will be correct on the standard part. We can therefore use that oracle we generated to compute $f$, and since $f$ is total, we will never need to reach into the nonstandard part of the oracle for any standard input. So $f$ will be computable with true nonstandard help.

Conversely, suppose that $f$ is a total function and computable with true nonstandard help by program $p$. It follows that $p$ on input $(n,H)$ gives output $f(n)$ with any nonstandard model of true arithmetic and any nonstandard $H$. Since any larger $H$ would also work, it follows that $p$ with input $(n,k)$ must give output $f(n)$ for all sufficiently large $k$, including sufficiently large standard $k$. In other words, $f(n)=m$ just in case there is $K$ such that for all $k\geq K$ program $p$ on input $(n,k)$ gives output $m$. This is a $\Sigma^0_2$-definable property, and so the theorem is proved. $\Box$

This theorem seems to answer the question concerning the exact complexity of having a nonstandard but arbitrary nonstandard auxiliary input.

Update. I've realized now that one may achieve a better interpretation by considering only models of true arithmetic. In this case, the notion will be much more powerful.

Let us define that a (partial) function $f$ on the natural numbers is computable by program $p$ with true nonstandard help, if in any nonstandard model $N$ of true arithmetic (that is, an elementary extension of the standard model) and any nonstandard number $H$ in $N$, the program $p$ on input $(n,H)$ halts in $N$ with output $f(n)$, if $n$ is in the domain of $f$, and otherwise does not halt.

One can now easily see that $0'$ and $0''$ and so on are computable with true nonstandard help. By iterating this, we can see that any arithmetically definable function is computable with true nonstandard help, and one can transcend this by uniformly computing the jumps. So $0^{+\omega}$ is computable with true nonstandard help, and thus true arithmetic itself is computable with true nonstandard help. And then one can iterate further, climbing into the hyperarithmetic hiearchy.