If language A is Mapping Reduced to language B (A $\le _m B$) and B is DECIDABLE, what can be concluded about A?
If B is decidable and A $\le _m B, we can decide A$ by reducing input x to f(x) and running B's decider on f(x).
What is the 'Modified Post Correspondence Problem' (MPCP)?
MPCP forces index selection to begin strictly with pair 1, serving as an intermediate bridge when reducing TM computation histories to PCP.
Are Post Correspondence Problem (PCP) and Modified Post Correspondence Problem (MPCP) equivalent in undecidability?
By padding domino characters with star delimiters (*), MPCP converts to standard PCP, proving both undecidable.
According to Rice's Theorem, which of the following properties of a Turing Machine language L(M) is DECIDABLE?
By Rice's Theorem, any property satisfied by some RE languages but not all RE languages (non-trivial) is completely undecidable.
What does Rice's Theorem Part 2 state regarding Monotone vs Non-Monotone properties of RE languages?
Rice's Theorem Part 2 classifies undecidable language properties: non-monotone properties (like emptiness or finiteness) yield Non-RE languages.