Ask your own question, for FREE!
Mathematics 13 Online
OpenStudy (anonymous):

Hi all of you. This question is related to automata theory. Consider 3 decision problems P1,P2,P3. It is known that P1 is decidable and P2 is undecidable. Then which of the following is true?? A)P3 is decidable if P1 is reducible to P3 B)P3 is undecidable if P3 is reducible to P2 C)P3 is undecidable if P2 is reducible to P3 D)P3 is decidable if P3 is reducible to P2's complement

OpenStudy (anonymous):

Its a very tricky question... In my opinion the answer would be B. because practically we can't say anything about a problem(ie. undecidable) if that problem is reducible to some other problem but if it would have been said in a reversed manner then the problem would then have become decidable... Reply if you have any query

Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!
Latest Questions
TJH: love Love, it comes, it goes But what if it stayed stayed in the silence the storm stayed when the world was loud for me it's different; it left when it was
5 days ago 4 Replies 3 Medals
Puffer: General question what came first the chicken or the egg itu2019s a trick question
5 days ago 5 Replies 1 Medal
Twaylor: would anyone mind helping me fix this in my code
1 week ago 9 Replies 0 Medals
TJH: Thank you to staff and admin for keeping this place running
23 hours ago 8 Replies 1 Medal
Bounty: the world keeps moving fast and I'm stuck in a time lapse all I need is a minute
1 week ago 4 Replies 0 Medals
Bounty: can I get so tips on how to start my journey into semi-realism art also on how to
2 weeks ago 0 Replies 0 Medals
Strawberryluna: Read my poem. Im not for criticism its a poem I wrote after my breakup: Youu2019ll never understand the way you made me break, I hate that I still love you
6 days ago 5 Replies 2 Medals
Bounty: first poem in a min- (tittle)? one moment i'm fine I smile till my face burns I laugh till I cant breath Then I cry I wonder where I went wrong I listen to
3 weeks ago 5 Replies 1 Medal
Twaylor: 3d printing a glider (for 150 pound 5'8 person - prolly should make it for up to
1 hour ago 7 Replies 0 Medals
cullenn: pitter patter sound of rain gently tapping my window tonight. calming, soothing, right? not for me.
3 weeks ago 2 Replies 0 Medals
Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!