This is a little curiosity that came up in a project I am working on, and I thought someone might have a nice way to see the answer.

Question. Can we uniformly compute $n$ from an oracle for the $n^{\rm th}$ jump $0^{(n)}$?

Of course, if we hard-code $n$ into our representation of $0^{(n)}$, then the answer will be yes. Similarly, if we use a $\Sigma_n$-truth predicate instead of $0^{(n)}$, which is of course Turing equivalent, then we can compute $n$ by looking at the syntactic complexity of the assertions in the oracle. We could also get negative answers by making finite changes to each $0^{(n)}$, which would preserve Turing equivalence at each level but destroy the uniform algorithm.

My question, instead, is about using the usual representation of $0^{(n)}$ as sets of halting Turing machine programs. Specifically, using some standard Turing machine architecture and encoding of Turing machine programs, let $0'$ or $0^{(1)}$ be the collection of Turing machine programs (construed as a set of natural numbers) that halt on empty input. For $n\geq 1$, let $0^{(n+1)}$ be the collection of oracle Turing machine programs (construed as a set of natural numbers) that halt on empty input using oracle $0^{(n)}$.

The question is whether there is a program $e$ such that on empty input, program $e$ with oracle $0^{(n)}$ outputs $n$. In other words, is there a computer program such that if you give it some $0^{(n)}$ as an oracle, it can recover $n$?

I believe that the answer will be yes, by designing certain programs that halt or don't halt in a such a way that one can determine what $n$ must be.

If the answer is affirmative, then we can also answer affirmatively the following question:

Question. Is $0^{(k)}$ uniformly computable from $0^{(n)}$ for any $n\geq k$?

That is, using the specific representations of $0^{(n)}$ I defined above, is there an oracle Turing machine program $e$ such that on input $k$, given oracle $0^{(n)}$ for any $n\geq k$, will write out the contents of $0^{(k)}$?

I expect that the answer is yes.

Well, I am a little embarrassed, but after having written out my question and thinking about it for a time, I now see how to answer it. Somehow, it wasn't as clear to me before. (Should I instead simply delete? If so, please comment.)

We can compute any oracle $A$ uniformly in $A'$, by the following process: for any number $k$, there is a program $p_k$ that on any input checks if $k$ is in the oracle, halting if it is and not halting if it isn't. Thus, $k\in A\iff p_k\in A'$, and the map $k\mapsto p_k$ is computable.

For any program $e$ to be used with oracle $A$, we can uniformly create a program $q_e$ to be used with $A'$, but computing the same function. Namely, $q_e$ on any input uses the method of the previous paragraph to simulate $e$ with oracle $A$, by systematically generating larger and larger fragments of the oracle $A$ from $A'$ in order to simulate $e$ with oracle $A$.

Now we simply iterate this process, so that from $0^{(n)}$ we can uniformly compute the preceding jumps $0^{(n-k)}$ for any given $k< n$. That is, we compute the jumps from the top down.

Finally, notice that the way that I defined $0^{(1)}$, it consisted of non-oracle programs only, and so we can determine with oracle $0^{(n)}$ whether $n=1$ or $n>1$ by looking at one of the programs in the oracle, and checking if it is an oracle program or a non-oracle program.

So, we simply systematically undo the jumps until we see that we have $0^{(1)}$ or not, counting the number of times, and thereby compute $n$.

  • If one prefers instead to define $0^{(0)}$ as empty and regard $0^{(1)}$ as the halting oracle programs with oracle $0^{(0)}$, then a similar idea works, by detecting $n=0$ with the program that searches for something in the oracle. – Joel David Hamkins Aug 24 '17 at 17:53
  • Joel, how can that work given the existence of intermediate Turing degrees per Post's problem? What if your oracle turns out to be one of those? – none Aug 28 '17 at 4:31
  • 1
    It is given that the oracle is one of the $0^{(n)}$, so it isn't one of those. – Joel David Hamkins Aug 28 '17 at 11:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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