Telling which turing machines halt using an Oracle

423 Views Asked by At

We have an oracle $T$, which on input $\langle M, w\rangle$ tells whether $M$ halts on $w$ or not(i.e. decides the halting problem). Now, given $\langle M_1, M_2...M_y, w\rangle$ as input, can we tell which of the machines halt on input $w$ by using $T$ at most $x$ times? Obviously, $x < y$.

Intuitively, we can test only some boolean function of $\langle C_1, C_2...C_y\rangle$ where $C_i$ denotes whether $M_i$ halts on $w$ using one instance of $T$. It seems undecidable. But, I cannot seem to give a formal proof.

1

There are 1 best solutions below

2
On BEST ANSWER

You can feed the oracle a TM that runs the $M_i$ in parallel and halts iff at least "$k$" of them halt, then binary chop based on $k$. Then once you know that exactly $k$ of them halt, run the $M_i$ yourself in parallel until $k$ halt, then you know exactly which ones halt. This means you only need $\lceil \log_2 (y+1) \rceil$ adaptive queries, i.e. $y\leq 2^x - 1$.

Conversely, if $y\geq 2^x$, you can show by a standard diagnoalisation argument that there are $M_1,\dots,M_y$ that fool a given algorithm for each of the $2^x$ possible oracle responses.