Theorem:
A (DFA) is a decidable language (accept)
Theorem:
A (NFA) is a decidable language (accept)
Theorem:
E (DFA) is a decidable language (empty)
Theorem:
EQ (DFA) is a decidable language (equal)
Theorem:
A (CFG) is a decidable language (accept)
Theorem:
E (CFG) is a decidable language (empty)
Theorem:
A (TM) is an undecidable language (accept)
The diagonalization method
R is uncountable
Some language is not Turing recognizable
The set of all Turing machines is countable
The set of all languages is uncountable.
Theorem:
A language is decidable if and only if it is both Turing-recognizable and co-Turing recognizable
A(TM) is not Turing recognizable.