If an oracle Turing machine halts with every infinite arithmetic oracle, can it fail to halt with some non-arithmetic oracle? Let $e$ be an index of an oracle Turing machine program and $k$ be some natural number. Let us say that a subset of $\mathbb N$ is arithmetic if it is definable in the model $\langle \mathbb N,+,\cdot,<,0,1\rangle$. Now suppose that there is a non-arithmetic oracle $A$ such that $\Psi_e^A(k)\uparrow$. Is it possible that $\Psi_e^B(k)\downarrow$ with every infinite arithmetic oracle $B$?
Note that it is not possible if we remove the key assumption that $B$ must be infinite. Suppose there is some non-arithmetic oracle $A$ so that $\Psi_e^A(k)\uparrow$. We can then consider the infinite binary tree $T$ consisting of all finite sequences $s$ such that $\Psi_e^B(k)$ does not halt with any oracle $B$ extending $s$ in less than length of $s$ many steps. The tree $T$ is arithmetic and therefore must have an arithmetic path $P$ (this follows from the proof of König's Lemma). Clearly $\Psi_e^P(k)\uparrow$. But of course $P$ can be finite! In this argument, there is no obvious way to guarantee that $P$ is infinite because it is possible to have an infinite arithmetic binary tree without an arithmetic path with infinitely many 1s.
 A: Consider an oracle Turing machine $M$ which enumerates its oracle $A=\{n_0<n_1<n_2<\dots\}$ by querying every $n\in\omega$ in increasing fashion, and whenever it hits a new element $n_k\in A$, it halts unless all the following conditions are met:


*

*$n_k$ is the Gödel number of a finite set $T_k$ of arithmetic sentences in prenex normal form.

*Every quantifier-free sentence from $T_k$ is true.

*If $k>0$, then $T_{k-1}\subseteq T_k$, and:


*

*For every $\ulcorner\exists x\,\phi(x)\urcorner\in T_{k-1}$, there is $m$ such that $\ulcorner\phi(\dot m)\urcorner\in T_k$.

*For every $\ulcorner\forall x\,\phi(x)\urcorner\in T_{k-1}$ and $m\le n_{k-1}$, we have $\ulcorner\phi(\dot m)\urcorner\in T_k$.

*For every prenex sentence $\phi$ with Gödel number less than $n_{k-1}$, $\ulcorner\phi\urcorner\in T_k$ or $\ulcorner\neg\phi\urcorner\in T_k$, where $\neg\phi$ denotes the sentence obtained from $\phi$ by dualizing every quantifier and negating its quantifer-free matrix.
If $A$ is an infinite oracle such that $M^A{\uparrow}$, it is easy to see that all sentences in any $T_k$ are true, and $\mathrm{Th}(\mathbb N)$ is Turing reducible to $A$. In particular, $A$ is nonarithmetic.
On the other hand, one can easily build an infinite $A$ (even Turing reducible to $\mathrm{Th}(\mathbb N)$) such that $M^A{\uparrow}$.
A: This is a really great question!
Here is a different way to think about Emil's example.
Consider the notion of a annotated truth predicate. This is a
labeling of every arithmetic sentence as true or false, in
accordance with Tarski's recursive truth requirements, but
annotated in the sense that whenever an existential sentence
$\exists x\, \varphi(x)$ is labeled as true, then a satisfying
witness $n$ is annotated right there, for which $\varphi(n)$ is
also labeled as true. Thus, an annotated truth predicate is a truth predicate, where the Skolem witnesses are provided, and you don't have to go search to see if the witnesses are really there.
Now, consider the Turing machine, which on any input begins to
inspect the oracle, to see if it is an annotated truth predicate.
Thus, on any input the program begins to check that all the
Tarskian truth conditions are met, that the atomic formulas are
labeled true or false correctly, that the Boolean combinations are
labeled correctly, and then, for the existential assertions, it
checks whether the annotations follow the rules. As long as these
conditions are being met, the program continues operating, but as
soon as a violation is found, then the program halts.
The point, now, is that because there is no arithmetic truth
predicate, there also is no arithmetic annotated truth predicate,
and so on any arithmetic oracle the program will eventually find a
flaw and therefore halt.
But meanwhile, there are annotated truth predicates (for example,
of hyperarithmetic complexity), and on these, the program will
never halt.
So this is a program with your desired features.
A: To give a more recursion-theoretic answer, the stronger statement in which "arithmetic" is replaced by "hyperarithmetic" also holds.  Take a recursive subtree $T$ of the finite increasing sequences of natural numbers such that $T$ has infinite paths but has no infinite hyperarithmetic path.  Consider the oracle Turing machine which halts relative to an oracle $X$ when it finds an initial segment $\sigma$ of the increasing enumeration of the elements of $X$ such that $\sigma$ is not an element of $T$.  This machine will halt on every infinite hyperarithmetic $B$ but not halt on any of the infinite paths in $T$.  
