3
$\begingroup$

Here is a quote from the Source 1:

For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the oracle.

But here is a quote from the Source 2:

If you have an oracle for the halting problem, then you can compute the Busy Beaver function. Given an input $n$, just search through all Turing machines with $n$ states and check whether they halt or not. For the TMs that halt, run them through to completion, and count the number of steps or symbols printed. Keep track of the maximum score. After you have run through all possible Turing machines, you will have the Busy Beaver number.

I can imagine how this would work for the first-order oracle machine simulating a no-oracle machine, but I cannot understand how an oracle machine of the arbitrary order would simulate the lower-order oracle machine, assuming that the simulated machine can also simulate another machine with the arbitrary level of "nested" oracles!

For example, consider the computation process of a 4th-order oracle Turing machine equipped with a halting oracle for the 3rd-order oracle Turing machine. At some moment the program starts simulating some program for, say, 2nd-order machine. But how does the oracle interprets the content on the oracle tape when the simulated program goes into ASK state? If the oracle interprets this content as the question for the 4-th order machine, then the simulation is absolutely meaningless because the answer would not correspond to the answer provided by the simulated (2nd-order) oracle.

But if the mathematically correct simulation cannot be performed, then how would an $x$-th-order Turing machine with a halting oracle for the $(x-1)$-th-order machine compute the Busy Beaver number of any $(x-y)$-th Turing machine (where $1 \geq y \geq x$ and $y$ is a natural number)?

If such simulations can be performed without logical paradoxes, then is it possible to provide a pseudocode (similarly to this answer) that shows how some 5-th order oracle Turing machine obtains a value of $BB_4(x)$, and then the value of $BB_2(x)$?

Improve this question
$\endgroup$
1
  • $\begingroup$ Tangentially, you should check out the general notion of the Turing jump. $\endgroup$
    – Noah Schweber
    Commented May 31, 2018 at 18:50

1 Answer 1

Reset to default
2
$\begingroup$

The halting problem $\mathrm{Halt}_O$ for Turing machine with oracle access to $O$ is the language consisting of all oracle Turing machines $M$ that halt on the empty input when the oracle calls are interpreted as membership in $O$. A Turing machine with access to $\mathrm{Halt}_O$ can compute the busy beaver number for oracle Turing machines with oracle access to $O$.

Now to your other question. Let $O_0 := \emptyset$, and $O_{i+1} = \mathrm{Halt}_{O_i}$ (so $O_i = 0^{(i)}$ using the usual terminology). Let us show that given oracle access to $O_{i+1}$ you can simulate oracle access to $O_i$. Consider the following program:

If $x \in O_i$ then halt, else run an infinite loop.

Using oracle access to $O_{i+1} = \mathrm{Halt}_{O_i}$ you can determine whether this program halts, which happens if and only if $x \in O_i$.

Applying this construction inductively, you can simulate access to $O_i$ given access to $O_j$ for all $j \geq i$. This shows that having an oracle for $O_j$ is indeed stronger than having an oracle for $O_i$ (when $i < j$).

Improve this answer
$\endgroup$
4
  • $\begingroup$ For example, let $M_{5.x}$ denote a particular 5th-order oracle machine (where $x$ is its index). The oracle answers the following question: "Does a machine $M_{4.n}$ halts on a blank input?" for any natural number $n$. But I cannot understand what is the algorithm that allows $M_{5.x}$ to obtain the value of $BB_4(k)$ (where $k$ is the number of states in $M_{4.n})$ or $BB_y(k)$ for any $y < 5$. $\endgroup$
    – lyrically wicked
    Commented Apr 10, 2018 at 7:29
  • $\begingroup$ The algorithm for computing the busy beaver function relativizes. It is exactly the same. $\endgroup$
    – Yuval Filmus
    Commented Apr 10, 2018 at 7:30
  • $\begingroup$ I edited the question. Consider two absolutely equal tables of instructions. If this table is given to a machine with the 5-th-order oracle, it will interpret the oracle tape in the first way. But if this table is given to a machine with the 2nd-order oracle, this lower-order oracle will interpret the oracle tape in the second way. $\endgroup$
    – lyrically wicked
    Commented Apr 10, 2018 at 7:48
  • $\begingroup$ I believe that my answer contains enough information for you to tackle this on your own. $\endgroup$
    – Yuval Filmus
    Commented Apr 10, 2018 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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