Lower bound on number of oracle calls for solving $n$ instances of the halting problem

Question

I encountered the following question, which is an easy exercise (spoiler below).

We are given $n$ instances of the halting problem (i.e. TMs $M_1,...,M_n$), and we need to decide exactly which of them halt on $\epsilon$. That is, we need to output $\{i: M_i\text{ halts on }\epsilon\}$. We are given an oracle for the halting problem, but we have to use it a minimal number of times.

It is not hard to show that it can be done with $\log (n+1)$ calls.

My question is: can we prove a lower bound? Is there reason to suspect that such a bound will be very hard to find?

The answer to the question itself (spoiler, hover mouse):

Consider the case of $3$ TMs. We can construct a TM $H_2$ that runs $M_1,M_2,M_3$ in parallel, and halts if at least two of them halt (otherwise it gets stuck). Similarly, we can construct a TM $H_1$ that halts if at least one of them halts. We can then call the oracle on $H_2$. If it halts, then we can run the machines in parallel, and wait for one to halt. We can then call the oracle on the last one. If the oracle says "no", then we run the oracle on $H_1$. If it halts, then we run the machines until one halts, and it's the only one that halts. If $H_1$ does not halt, then none of them halt. Extending this to $n$ machines is easy.

The first observation about this question is that it seems impossible to solve using information-theoretic tools, since we crucially rely on our ability to obtain information by running the machines without the oracle.

Answer 1

The result can be found in

• Beigel, R., Gasarch, W. I., Gill, J., and Owings, J. Terse, superterse, and verbose sets. Inform. and Comput. 103 (1993), no. 1, 68–85.

Their proof in fact shows that your problem cannot be solved with fewer than $\log_2 n$ queries to any set $X$, let alone to the halting problem itself. For some notation, your problem is sometimes denoted $C_n^K$ or $C_n^{HALT}$ (depending on your favorite notation for the halting problem).

For this and many related results, see also:

• This survey by Gasarch

• The book Bounded Queries in Recursion Theory by Gasarch and Martin.

Answer 2

EDIT: The argument that I had answered with was not wrong, but it was a bit misleading, in that it only showed that the upper bound had to be tight for some $n$ (which is actually trivial, since it has to be tight when $n=2$ and the bound is 1).

Here is a more precise argument. It shows that if the upper bound of $\log_2 n$ is loose for any particular $n$, then for all $n$ the number of oracle calls required is $O(1)$.

(Surely it is not $O(1)$, so the upper bound is never loose! But I don't actually prove that here, and given the other answer to the problem, it doesn't seem worth pursuing.)

Consider the problem of computing the maximum output:

Given an $n$-tuple $(M_1,\ldots,M_n)$ of Turing machines, compute the maximum output (of the Turing machines that halt, if run on $\epsilon$). If none of them halt, return 0.

As a function of $n$, the worst-case number of oracle calls required to compute this function is the same as the number required to decide which of $n$ given machines halt. (If I know which machines halt, I can easily compute the maximum output. Conversely, if I want to know which machines halt, following the construction in the problem statement, I can construct machines $\{M'_i\}$ $(i=1,2,\ldots,n)$ where $M'_i$ runs all of the $n$ given machines in parallel, then halts and output $i$ if $i$ of them ever halt. The maximum output will tell me the number that halt. From that I can compute exactly which halt.)

Now, let $n_0$ be the smallest integer $n$ (if any) such that the following holds:

Using $C(n) = \max\{k \in \mathbb{Z} : 2^k < n\}$ oracle calls, one can compute the maximum output of $n$ given machines. (That is, the upper bound is not tight for $n$.)

Clearly $n_0>1$, because $C(1) = -1$. In fact, $n_0>2$ also, because $C(2) = 0$, but it is undecidable to compute the maximum output of $2$ given machines (with no oracle calls). Now consider larger $n$:

Claim: If $n_0$ is finite, then, for any $n$, one can compute the maximum output of $n$ given machines in $C(n_0)$ oracle calls. (Note that if $n_0$ is finite, then $C(n_0) = O(1)$.)

Proof.. We prove it by induction on $n$. The base cases are $n\le n_0$, which hold by definition of $n_0$ and $C$.

Let $Q_0$ be the TM that, given any $n_0$ Turing machines, computes the maximum output using only $C(n_0)$ calls to the oracle.

Fix any $n>n_0$. Given any $n$ machines $M_1,\ldots, M_n$, compute the maximum output as follows.

Focus on the first $M_1,\ldots,M_{n_0}$ machines. Consider running $Q_0$ on these $n_0$ machines. Note that $Q_0$ makes $C(n_0)$ calls to the oracle, and there are only $n' = 2^{C(n_0)}$ possible responses by the oracle to these calls. Note that by definition $n' = 2^{C(n_0)} < n_0$. Let $o_i$ denote the $i$th possible response. For each $i=1,\ldots,n'$, construct a machine $M'_i$ that simulates $Q_0$ on these machines as follows:

TM $M'_i$ (on input $\epsilon$):

1. Simulate $Q_0$ on the $n_0$ machines $(M_1,\ldots,M_{n_0})$, but instead of calling the oracle, assume the oracle responds according to $o_i$.
2. This simulation might not halt (e.g. if $o_i$ is not what the oracle would actually return).
3. If the simulation halts, let $h_i$ be the maximum output that $Q_0$ says would be given.
4. Dovetail all $n_0$ machines $(M_1,\ldots,M_{n_0})$. If one of them ever outputs $h_i$, stop and output $h_i$.

Now, in the given sequence of $n$ machines, replace the first $n_0$ machines $M_1,\ldots,M_{n_0}$ by these $n'< n_0$ machines $M'_1,\ldots,M'_{n'}$. Return the value computed by recursing on this sequence of $n-(n_0-n') < n$ machines. (Note that the oracle is not called before recursing, so that the oracle is only called once the base case is reached.)

Here is why this computation is correct. For the $i$ such that $o_i$ is the ``correct'' response by the oracle $Q_0$ to the queries, $M'_i$ would halt and give the correct maximum output of the original $n_0$ machines. Thus, the maximum output of the $n'$ machines $(M'_1,\ldots,M'_{n'})$ is at least the maximum output of the $n_0$ machines $(M_1,\ldots,M_{n_0})$. On the other hand, by step 4, no $M'_i$ can give an output that is larger than the maximum output of $(M_1,\ldots,M_{n_0})$. Thus, the maximum output of the $n'$ machines $(M'_1,\ldots,M'_{n'})$ equals the maximum output of the $n_0$ machines that they replace. QED