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.

Related Posts

Comments are closed.

© 2023 Software Engineering - Theme by WPEnjoy · Powered by WordPress