Automata Theory 简明教程

Undecidable Languages

对于不可判定的语言，不存在接受该语言和对每个输入串 w 做出判定的图灵机（尽管 TM 可以对某些输入串做出判定）。如果对 P 的所有肯定实例的语言 L 是不可判定的，则判定问题 P 称为“不可判定”。不可判定语言不是递归语言，但有时可能是递归可枚举语言。

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.

undecidable languages

Example

  1. The halting problem of Turing machine

  2. The mortality problem

  3. The mortal matrix problem

  4. The Post correspondence problem, etc.