Math and science::Theory of Computation

# Examples of decidable and undecidable languages

Consider the decidability and recognizability of some specific languages. All the below languages *represent
answers* to certain questions. If one of the languages is decidable, then
the corresponding question can be answered definitively in finite time by a
Turing machine.

The acronyms used below are:

- DFA
- Deteministic finite automaton
- NFA
- Non-deterministic finite automaton
- CFG
- Context free grammar
- TM
- Turning machine
- Linear bounded machine
- Linear bounded machine (TM with finite memory).

Given a DFA, \( B \), and a string, \( w \), does \( B \) accept \( w \)? | \( A_{\text{DFA}} = \{ \langle B, w \rangle | \text{$B$ is a DFA that accepts input string $w$} \} \) | Decidable |

Given a NFA, \( B \), and a string, \( w \), does \( B \) accept \( w \)? | \( A_{\text{NFA}} = \{ \langle B, w \rangle | \text{$B$ is a NFA that accepts input string $w$} \} \) | Decidable |

Given a CFG, \( G \), and a string, \( w \), does \( G \) generate \( w \)? | \( A_{\text{CFG}} = \{ \langle G, w \rangle | \text{$G$ is a CFG that generates input string $w$} \} \) | Decidable |

Given a TM, \( M \), and a string, \( w \), does \( M \) accept \( w \)? | \( A_{\text{TM}} = \{ \langle M, w \rangle | \text{$M$ is a TM that accepts input string $w$} \} \) | Undecidable, but recognizable |

Given a LBA, \( M \), and a string, \( w \), does \( M \) accept \( w \)? | \( A_{\text{LBA}} = \{ \langle M, w \rangle | \text{$M$ is a LBA that accepts input string $w$} \} \) | Decidable! |

Given a DFA, \( B \), is the language of \( B \) empty? | \( E_{\text{DFA}} = \{ \langle B \rangle | \text{$B$ is a DFA and $\operatorname{L}(B) = \emptyset$} \} \) | Decidable |

Given a CFG, \( G \), is the language of \( G \) empty? | \( E_{\text{DFA}} = \{ \langle G \rangle | \text{$G$ is a CFG and $\operatorname{L}(G) = \emptyset$} \} \) | Decidable |

Given a TM, \( M \), is the language of \( M \) empty? | \( E_{\text{TM}} = \{ \langle M \rangle | \text{$M$ is a TM and $\operatorname{L}(M) = \emptyset$} \} \) | Undecidable |

Given a LBA, \( M \), is the language of \( M \) empty? | \( E_{\text{LBA}} = \{ \langle M \rangle | \text{$M$ is a LBA and $\operatorname{L}(M) = \emptyset$} \} \) | Undecidable |

Given two DFAs, \( A \) and \( B \), do they recognize the same language? | \( EQ_{\text{DFA}} = \{ \langle A, B \rangle | \text{$A$ and $B$ are DFAs and $\operatorname{L}(A) = \operatorname{L}(B)$} \} \) | Decidable |

Given two CFGs, \( A \) and \( B \), do they recognize the same language? | \( EQ_{\text{CFG}} = \{ \langle A, B \rangle | \text{$A$ and $B$ are CFGs and $\operatorname{L}(A) = \operatorname{L}(B)$} \} \) | Undecidable |

Given two TMs \( M_1 \) and \( M_2 \), do they recognize the same language? | \( EQ_{\text{CFG}} = \{ \langle M_1, M_2 \rangle | \text{$M_1$ and $M_2$ are TMs and $\operatorname{L}(M_1) = \operatorname{L}(M_2)$} \} \) | Undecidable |

Given a Turing machine, \( M \), does it halt on a given input? | \( HALT_{\text{TM}} = \{ \langle M, w \rangle | \text{$M$ is a TM and accepts or rejects $w$} \} \) | Undecidable |

Given a Turning machine \( M \), does it recognize the same language as a DFA? | \( REGULAR_{\text{TM}} = \{ \langle M \rangle | \text{$M$ is a TM and $\operatorname{L}(M)$ is a regular language.} \} \) | Undecidable |

Interesting point: the complement of \( A_{\text{TM} } \), \( \overline{A_{\text{TM} } } \), isn't even recognizable!