World's most popular travel blog for travel bloggers.

[Solved]: Reducibility in Computability Theory

, , No Comments
Problem Detail: 

In Sipser's book of Theory of Computation, related to Reducibility, it's written

if A is undecidable and reducible to B, B is undecidable.

The confusion is, only a solution to B determines a solution to A, if i'm not wrong. So, for instance if B is decidable and A is undecidable, what does it mean? Here B isn't undecidable.

Hope you got it.

Asked By : Abdussami Tayyab

Answered By : Yuval Filmus

Suppose $A$ is undecidable and reducible to $B$. Given an algorithm for $B$, you can use the reduction from $A$ to $B$ to get an algorithm for $A$, which we assumed is impossible. Therefore $B$ must be undecidable.

If $A$ is undecidable and reducible to $B$ and $B$ is decidable then we obtain a contradiction and everything goes. Pigs can fly.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback