My question is about Halting Problem

Question

Imagine for the sake of this question that Sheikh Chilly is capable of solving HALT. Given any instance of ‹M, w› to the Halting problem, we can query Sheikh Chilly if ‹M, w› ∈ HALT, and he will instantaneously give us the right answer. This method can be used to solve k instances ‹M1, w1›, ‹M2, w2›. . .‹Mk, wk› to the halting problem by asking Sheikh Chilly k questions. In fact, we can do better! Show that we can solve three instances ‹M1, w1›, ‹M2, w2› and ‹M3, w3› to Halting problem by querying Sheikh Chilly only twice. We can only give Sheikh Chilly questions of the form, “Is ‹M, w› ∈ HALT?

Answer 1

Form two new programs C1(M1, M2, M3) and C2(M1, M2, M3).

C1 and C2 execute their given three programs in parallel, or

interpret them by dove-tailing, or whatever is your favorite way of executing

multiple programs simultaneously.

C1 and C2 let the given three programs consume their input, and

whenever any one of the given three programs terminates C1 and C2 print

which one terminated.

C1 itself will terminate as soon as any one of the given three programs terminates.

C2 itself will terminate as soon as any two of the given three programs terminate.

First ask Sheikh Chilly whether <C2(M1,M2,M3), (w1,w2,w3)> terminates.

If he says "yes" then run <C2(M1,M2,M3), (w1,w2,w3)> and see which

two of the three terminate.

Then use your second question to determine termination of the remaining one.

If he says "no" to the first question,

then ask him whether <C1(M1,M2,M3), (w1,w2,w3)> terminates.

If he says "yes" to this second question then run <C1(M1,M2,M3), (w1,w2,w3)> to see which one terminates.

And we know that the other two do not terminate

(since the answer to the first question was "no").

If he says "no" to the second question then none of the three terminates.