Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
