Detecting if three Turing Machines halt given a magic oracle that is only used twice

Question

We were given a question in class as follows:

You have a "magic oracle" that can decide if a Turing Machine halts. You have three TMs $T_1, T_2, T_3$. Device an algorithm that decides which of the TMs halt and which do not by asking the oracle at most twice.

The sketch of the solution given was

Construct a new TM $T_A$ that terminates if at least 2 TMs (from $T_1, T_2, T_3$) halts. Construct a new TM $T_B$ that terminates if one TM halts.

First call oracle on $T_A$. If $T_A$ halts: Run $T_1, T_2, T_3$ in parallel until two of them halt, then call the oracle on the last TM that does not finish running.

If $T_A$ doesn’t halt:

Call oracle on $T_B$, If $T_B$ halts: Then run $T_1, T_2, T_3$ in parallel until one of them halts. That TM is the only one that halts

If $T_B$ does not halt: then $T_1, T_2, T_3$ all do not halt.

---

I did not agree with this solution, as formalising the proof would mean $T_A$ and $T_B$ are Oracle Turing Machines that must ask the oracle about the termination of $T_1, T_2, T_3$. The professor replied

They don't use magic oracles internally, because they are not claimed to detect termination, they just terminate if and only if other machines terminate, which can be achieved through concurrent interpretation of that machines.

Is this right? How would you go about formalising this? Thanks.

Answer 1

One way to built $T_A$ works is roughly as follows:

While (true) {
   run $T_1$ for 10 steps, if $T_1$ halts during that time, $i := 1$, break;
   run $T_2$ for 10 steps, if $T_2$ halts during that time, $i := 2$, break;
   run $T_3$ for 10 steps, if $T_3$ halts during that time, $i := 3$, break;
}

While (true) {
   if not $i = 1$
       run $T_1$ for 10 steps, if $T_1$ halts during that time, break;
   if not $i = 2$
       run $T_2$ for 10 steps, if $T_2$ halts during that time, break;
   if not $i = 3$
       run $T_3$ for 10 steps, if $T_3$ halts during that time, break;
}

halt

As you see, there is no magic involved.

Answer 2

As Arno shows in the other answer, you can easily write a program that halts if and only if at least $k$ out of $n$ given Turing machines halt, by running the $n$ machines in parallel until $k$ of them have halted. As a bonus, if you actually run this program (instead of just asking the oracle about it), it will tell you which ones were the $k$ it found to halt.

So if someone gives you $2^{n}-1$ Turing machines, and an oracle that will tell you whether a given TM will halt, you can do a binary search with the oracle, using it just $n$ times, to determine exactly how many of the TM's halt. Once you know this number, then you can actually run the program for this $k$ to figure out which ones halt.

If $k=2$, this solves the stated problem, only slightly differently from the provided solution.

Although it might sound like this is a general procedure that reduces $2^n-1$ oracle queries down to just $n$ oracle queries, and so by repeating the reduction you could arbitrarily reduce the number of queries, that doesn't actually work, because each of the $n$ queries you make depends on the results of the previous queries, whereas the $2^n-1$ machines do not depend on each other.

Answer 3

The key point here is that $T_A$ and $T_B$ does not know whether any of the TMs will halt. It just simulates all TMs, and it will halt if 2 of them (1 for $T_B$) halt. If none of them halt, then $T_A$ also won't halt, which is why $T_A$ and $T_B$ are not oracle, since they are not guaranteed to halt, unlike the actual oracle, which is guaranteed to halt and give an answer.