6. Bonus 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) E HALT, and he will instantaneously give us the right answer. This method can be used to solve k instances (M1, wi), (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) E HALT? 6. Bonus 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) E HALT, and he will instantaneously give us the right answer. This method can be used to solve k instances (M1, wi), (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) E HALT