Practice Theory of Computation - GATE - CSIT, DSAI & Placements Offered by Unacademy

Theory of Computation

$X \leq_{m} Y$ denotes that a language X is mapping reducible to language Y. Given that $X \leq_{m} Y$ and $Y \leq_{m} Z$ .

Consider the statements given below

S1: If Z is decidable then X and Y are decidable.

S2: If Y is decidable then X and Z are decidable.

S3 If Z is undecidable then X and Y are undecidable.

S4 If X is decidable then Y and Z are decidable.

Which of the above statements are TRUE

Only S3

Only S2 and S4

Only S1

Only S1 and S3