If a language L and its complement L' are BOTH Recursively Enumerable, what class does L belong to?
By Post's Theorem, if L and L' are both RE, running TMs for L and L' in parallel guarantees one will halt, proving L is Recursive.
What is the famous 'Halting Problem' formulated by Alan Turing?
The Halting Problem asks if a general algorithm can decide whether any given TM halts on input w.
Is the Halting Problem Decidable or Undecidable?
Alan Turing proved in 1936 via diagonalization that no general algorithm can solve the Halting Problem for all TMs.
What does 'Rice's Theorem' state regarding non-trivial semantic properties of Recursively Enumerable languages?
Rice's Theorem asserts that any non-trivial semantic question about what language a TM accepts (e.g. is L(M) empty, finite, regular, context-free) is undecidable.
Which of the following decision problems regarding Turing Machines is UNDECIDABLE?
By Rice's Theorem, testing emptiness, finiteness, or membership for general Turing Machines is completely undecidable.