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.



If an oracle Turing machine halts with every infinite arithmetic oracle, can it fail to halt with some non-arithmetic oracle?
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}$.


