Q5Theory of Computation
Question
10 marks
Discuss the decidability and undecidability of languages. Explain Rice's Theorem.
Answer
Rice's Theorem: Properties of RE languages are undecidable.
Rice's Theorem states that any non-trivial semantic property of the language recognized by a Turing machine is undecidable. Examples of undecidable problems: Emptiness, Finiteness, Equivalence of TMs.