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.

  • 1
    $\begingroup$ In case someone else is also confused by the last sentence: every arithmetic infinite binary tree of course has an infinite arithmetic path, but not necessarily one with infinitely many 1s. $\endgroup$ Sep 4, 2013 at 17:10

3 Answers 3


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}$.


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$.


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.

  • 1
    $\begingroup$ For more definiteness, one could say that the oracle lists out the true sentences, one after the other, in some canonical order. The annotation witnesses should be given as the empty space between two markers, so that failing to end the annotation leads to a finite oracle. $\endgroup$ Sep 5, 2013 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.