A clear explanation and proof of Rice’s Theorem followed by a worked out example.

Formal definition of property of the language of Turing Machines along with examples.

Venn diagram showing relative positions and examples of different type of languages.

Decidable languages are closed under complement. Recognizable languages that are closed under complement are decidable.

Checking the equivalence of two languages is undecidable. ETM reduces to EQTM.

Checking whether the language of a Turing Machine is empty is undecidable. ATM reduces to ETM.

The halting problem is undecidable. ATM reduces to HALTTM.

Checking whether a TM accepts a string is undecidable. Here is how.

Checking whether a context free language is empty is decidable. Here is how.

Checking whether a string belongs to a context free language is decidable. Here is how.