Ask your own question, for FREE!
Mathematics 6 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
serenitystXrgazer: Getting sent to anti gay christian covestion camp in a few weeks, any tips. guys i think im cooked.
3 hours ago 1 Reply 0 Medals
heartlessprophet: How do i get paid from work when im in job court ?
1 day ago 0 Replies 0 Medals
Aubree: Guys, what does love feel like? I've been getting a tight chest and when I talk to him my heart rate hangs out around 100-120 beats per min, and when he doe
10 hours ago 10 Replies 2 Medals
KBaby: Any1 down to call
2 days ago 0 Replies 0 Medals
KBaby: Bored af lwk need sum1 to talk to
2 days ago 2 Replies 0 Medals
thereneelg: ok... anyone have advice?? ...I did Choir all throughout Middle school and have ALWAYS been put in Soprano those three years.
2 days ago 6 Replies 1 Medal
kamariana: The Byzantine Procopius is known for (5 points) reconquering much of the old Roma
3 days ago 0 Replies 0 Medals
chuckD: hellp!!! what does it mean to describe a scientist as skeptical Why is sceptical
3 days ago 2 Replies 1 Medal
DoltonCarlee: So like do y'all know anything about the first world war?
2 days ago 2 Replies 0 Medals
thehearken: anyone know how to explain this so its easier for me to understand? b(1)=2, b(n)=
2 days ago 5 Replies 2 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!