Let us consider Turing machines (or other Turing-complete model of computation) that, in addition to their regular input, are given some integer $H$, where $H$ is positive nonstandard. This means, in particular, that $H$ is greater than any standard integer. What would be the Turing degree of such a machine?
The machine can solve the halting problem for standard turing machines. To see this, just run a machine for $H$ steps. If it halts before $H$ steps, the machine halts, of course. If it has not halted by then, it never will (since a halting standard turing machine always halts after a standard number of steps).
In fact, it can solve the halting problem for the $0^{(n)}$ (for standard integer n). We use the following algorithm, we which assume inductively takes less than $H^{n}$ steps for the $0^{(n-1)}$ Turing jump:
- Begin simulating the turing machine.
- Anytime the machine accesses its oracle to solve the halting problem for $0^{(n-1)}$, determine if whether or not it halts. This will take less than $H^{n}$ steps.
- After $H^{n+1}$ steps, if the machine has not halted yet, it never will.
To see this, note that a halting standard $0^{(n)}$ machine can only take a standard number $c$ of steps, and access its oracle a standard number $d$ times, and $c+dH^n<H^{n+1}$.
To be more specific, when I say the Turing degree of such a machine, I mean the machine with an oracle that can simulate such a machine on any standard input (it may diverge on nonstandard input). We also only consider them able to solve decision problems.
Note: When I talk about nonstandard integers, I have something like this in mind.