Undecidable Languages

For an undecidable language, there is no Turing Machine which accepts the language and makes a decision for every input string w (TM can make decision for some input string though). A decision problem P is called “undecidable” if the language L of all yes instances to P is not decidable. Undecidable languages are not recursive languages, but sometimes, they may be recursively enumerable languages.

Example

• The halting problem of Turing machine
• The mortality problem
• The mortal matrix problem
• The Post correspondence problem, etc.