Lower bound on number of oracle calls for solving $n$ instances of the halting problem 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.
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.