Which mathematical technique was used by Alan Turing to prove the undecidability of the Halting Problem?
Turing constructed a self-referential machine H' using Cantor's diagonalization principle to demonstrate a logical contradiction.
Rice's Theorem states that any non-trivial semantic property of Recursively Enumerable languages is:
Rice's Theorem proves that checking any non-trivial property regarding the language recognized by a TM (semantic property) is undecidable.
Is the class of Recursive Languages (REC) closed under Complementation?
A decider for L' can be made by running the decider for L and swapping 'accept' and 'reject' states. Thus REC is closed under complement.
Is the class of Recursively Enumerable Languages (RE) closed under Complementation?
If an RE language L and its complement L' were both RE, then L would be Recursive. Since non-recursive RE languages exist, RE is NOT closed under complement.
If a language L and its complement L' are BOTH Recursively Enumerable (RE), then L is:
Post's Theorem states that a language L is Recursive if and only if both L and L' are Recursively Enumerable.