The Beard Sage

  • Machine Learning
  • Computer Architecture
  • Theoretical Computer Science
  • About Me

Post Category → Theoretical Computer Science

Rice’s Theorem

posted in Theoretical Computer Science on April 25, 2020 by TheBeard 0 Comments

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

Continue reading →

Property of the language of Turing Machines

posted in Theoretical Computer Science on April 24, 2020 by TheBeard 0 Comments

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

Continue reading →

Venn Diagram of Languages with Examples

posted in Theoretical Computer Science on April 23, 2020 by TheBeard 0 Comments

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

Continue reading →

Closure under Complement: Decidable and Recognizable languages

posted in Theoretical Computer Science on April 22, 2020 by TheBeard 0 Comments

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

Continue reading →

Undecidable Language : EQTM

posted in Theoretical Computer Science on April 21, 2020 by TheBeard 0 Comments

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

Continue reading →

Undecidable Language : ETM

posted in Theoretical Computer Science on April 20, 2020 by TheBeard 0 Comments

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

Continue reading →

Undecidable Language : HALTTM

posted in Theoretical Computer Science on April 19, 2020 by TheBeard 0 Comments

The halting problem is undecidable. ATM reduces to HALTTM.

Continue reading →

Undecidable Language : ATM

posted in Theoretical Computer Science on April 18, 2020 by TheBeard 0 Comments

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

Continue reading →

Decidable Languages : ECFG, EPDA

posted in Theoretical Computer Science on April 17, 2020 by TheBeard 0 Comments

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

Continue reading →

Decidable Languages : ACFG, APDA

posted in Theoretical Computer Science on April 16, 2020 by TheBeard 0 Comments

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

Continue reading →
← Older posts
Copyright (C) 2021. All rights reserved.