14 - Decidability

ucla | CS 181 | 2024-06-05 14:13

---

Table of Contents

• Is a Language Decidable?
• Undecidable
  • Rice’s Theorem

Is a Language Decidable?

• lang $L$ is decidable $⟺$ $L,\bar{L}$ are both recognizable
• $⟹$ is trivial
• $⟸$ can be proved by running $M(L)$ and $M(\bar{L})$ in parallel, and one of them will halt
• Note, $L(M)$ is the language $M$ recognizes, but if M happens to decide it as well, it is always equivalent to $L$

  Undecidable

• $L=w:w\notin L(M_w)$ is not recognizable, and thus not decidable
• $HALT$ lang is recognizable but not decidable
• $\overline{HALT}$ is not recognizable

  Rice’s Theorem

  If some subset of Turing Recognizable languages, $\mathcal{C}\ne \mathrm{\varnothing }$ and $\bar{\mathcal{C}}\ne \mathrm{\varnothing }$ then $L={:L(M)\in \mathcal C\}$ is undecidable