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

Continue reading# Post Category → Theoretical Computer Science

# Property of the language of Turing Machines

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

Continue reading# Venn Diagram of Languages with Examples

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

Continue reading# Closure under Complement: Decidable and Recognizable languages

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

Continue reading#
Undecidable Language : EQ_{TM}

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

Continue reading#
Undecidable Language : E_{TM}

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

Continue reading#
Undecidable Language : HALT_{TM}

The halting problem is undecidable. ATM reduces to HALTTM.

Continue reading#
Undecidable Language : A_{TM}

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

Continue reading#
Decidable Languages : E_{CFG}, E_{PDA}

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

Continue reading#
Decidable Languages : A_{CFG}, A_{PDA}

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

Continue reading