LOOP = {<M,w1,w2,w3>: M is a Turing machine that doesn't halt on at least 2 of the wi}
HPC = {<M,w> : M is a Turing machine that doesn't halt on w}

Show that LOOP is polynomial time Turing reducible to HPC
I am not sure how to begin solving this kind of problem. Also the question I am trying to solve brings up the definition of A is polynomial reducible
to B if there is a B-oracle poly time Turing M such that M(x) accepts x iff x is in A.

Any hints or pointers on this ?

My thoughts :
What I understand by reducibility here is that If I have a Turing machine for HPC
Then I can use this turing machine to determine if <M,w1,w2,w3> is in LOOP
And same the other way If I have a turing machine for LOOP then I can use it
as a determiner for HPC. Is this a correct way to think about it?
This way it becomes simple and probably easier to prove. But not sure if it
is same as the question that is being asked


1 Answer 1


The question is given you have an oracle machine/black box for HPC can you decide if <M,w1,w2,w3> is in LOOP.

See the wikipedia page on that: https://en.m.wikipedia.org/wiki/Reduction_(recursion_theory)#Turing_reducibility

The proof is very straightforward as you already know.

  • $\begingroup$ So if you have an oracle turing machine for HPC say HPC-OT. Now given <M,w1,w2,w3> I can run HPC-OT on <M,w1> , <M,w2>, <M,w3> one by one and if it accepts at least two of these then <M,w1,w2,w3> is in LOOP. This is the simplest way to think. But does it classify as a formal proof. Do you think there is anything missing here ? Something I need to specify more $\endgroup$ Commented Mar 28, 2021 at 18:35
  • $\begingroup$ @Amit wadhwa I think this proof is fine. $\endgroup$ Commented Mar 29, 2021 at 11:40

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.