Basics of decidability

State whether each of the following statements are TRUE or FALSE. Your answers should be accompanied by a proof.

  • Every recognizable set has a decidable subset.

  • Any subset of a recognizable language is also recognizable.

  • \(\Sigma^*\) is decidable.

  • Any language over \(\Sigma\) is either decidable or recognizable

  • The complement of a decidable language is decidable.

Source: folklore

Related Content