Undecidable Languages - Automata Theory

What are undecidable Languages?

For an undecidable dialect, there is no Turing Machine which acknowledges the dialect and settles on a choice for each info string w (TM can settle on choice for some information string however). While any choice issue P is called as "undecidable". In any case, if the dialect L of all yes examples to P isn't yet decidable. Undecidable dialects are not recursive dialects, but rather in some cases, they might be recursively enumerable dialects.

undecidable

Example

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

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics