Raxone K.

asked • 05/16/21

My question is about Halting Problem

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?

1 Expert Answer


Daniel B. answered • 05/16/21

4.6 (21)

PhD in Computer Science with 42 years in Computer Research

Still looking for help? Get the right answer, fast.

Ask a question for free

Get a free answer to a quick problem.
Most questions answered within 4 hours.


Find an Online Tutor Now

Choose an expert and meet online. No packages or subscriptions, pay only for the time you need.