Decidability

https://en.wikipedia.org/wiki/Decidability_(logic)

A Decision Problem which can be solved by an algorithm is called Decidable.

• Propositional Logic is Decidable
  • For any argument $p_1,p_2,p_3\models q$, there exists an algorithm/computer program to determine if it is a valid argument or not
• Predicate Logic is undecidable
  • Predicate logic is semi-decidable. We can enumerate all the proofs and we will eventually find a proof if the argument is valid. However, if argument is invalid, there is no guarantee that the algorithm will terminate

From CS241E, we briefly explored the idea of Decidable languages in our exploration in Formal Languages:

• Decidable languages are sets of words for which there exists an algorithm that decides membership, i.e., decides whether or not some given word is in the set. Decidable and undecidable languages are studied in depth in CS 341

All regular and Context-Free Languages are Decidable.