11
$\begingroup$

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.

$\endgroup$
4
  • 5
    $\begingroup$ I'm not arguing that the proposed solution is wrong. But if you can create new Turing Machines, then why not make it simpler: Construct a new TM TC that terminates if all TMs in T1, T2, T3 halt. Now just call the oracle on TC. $\endgroup$ Feb 1, 2023 at 0:27
  • 20
    $\begingroup$ @QuantumMecha While the OP's description isn't clear, the OP is actually asked "tell me which one of T1 T2 and T3 halt or do not halt. Only call the oracle at most twice." I can tell this because (a) this is an actually interesting question, (b) it matches the solution provided, and (c) I can see how minor transcription errors could lead to the above. $\endgroup$
    – Yakk
    Feb 1, 2023 at 1:47
  • $\begingroup$ I take it you mean "determine, for each TM, whether it halts"? "decide(A halts and B halts and C halts)" is rather different from "decide(A halts) and decide(B halts) and decide(C halts)". $\endgroup$ Feb 1, 2023 at 4:19
  • $\begingroup$ @Acccumulation that seems to be the case, yea. We need to know the halting status for each of the three TM. $\endgroup$
    – justhalf
    Feb 1, 2023 at 8:02

3 Answers 3

18
$\begingroup$

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.

$\endgroup$
15
  • 9
    $\begingroup$ @minnmass: That requires introducing a notion of "seconds" or "millenia" and a way to measure them, which is outside the formalism of Turing machines. In contrast, a Turing machine simulating the operation of another Turing machine can easily do so for a defined number of steps. $\endgroup$ Feb 1, 2023 at 7:06
  • 2
    $\begingroup$ Nice. Just curious, why 10 steps though? Usually it's just 1 step. I mean, they're equivalent, but just curious as I never saw people using other than 1 step in this kind of proofs before. $\endgroup$
    – justhalf
    Feb 1, 2023 at 8:04
  • 1
    $\begingroup$ @minnmass: Also, the "wrapper" machine has to see the steps of the "wrapped" machines, because it is the one carrying out those steps. The code of the wrapper machine is made by refactoring and combining the code of the wrapped machines. $\endgroup$
    – Matt
    Feb 1, 2023 at 8:20
  • 1
    $\begingroup$ @justhalf: That's why I said it's up to you. :-) This won't be the last time you will see people doing things in a slightly more efficient way even when it doesn't affect the theoretical result. You could even run one machine for 1 step and another for 100 steps each time, the theory doesn't care. Any actual program will contain many stylistic decisions like this that don't matter. $\endgroup$
    – Matt
    Feb 1, 2023 at 8:29
  • 1
    $\begingroup$ @justhalf: Ah, then I misunderstood your comment! Sorry! I thought you already understood that it is just a stylistic decision, since you already understood that "they're equivalent", and you were just curious why anybody would actually make that stylistic decision. :-) $\endgroup$
    – Matt
    Feb 1, 2023 at 8:38
8
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.