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, |
Decidable | |
Given a NFA, |
Decidable | |
Given a CFG, |
Decidable | |
Given a TM, |
Undecidable, but recognizable | |
Given a LBA, |
Decidable! | |
Given a DFA, |
Decidable | |
Given a CFG, |
Decidable | |
Given a TM, |
[...] | |
Given a LBA, |
[...] | |
Given two DFAs, |
[...] | |
Given two CFGs, |
[...] | |
Given two TMs |
[...] | |
Given a Turing machine, |
[...] | |
Given a Turning machine |
[...] |