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.