theoryturing-machinescomputability

What are all known languages that Turing machines cannot accept?


For example, the language of Turing machines that do not accept their own encoding cannot be accepted by any Turing machine.


Solution

  • There are infinitely many languages that no TM can decide. Indeed, "most" languages are undecidable; there are countably many decidable languages, but uncountably many languages (hence, uncountably many undecidable ones).

    Rice's theorem allows you to come up with lots of examples of languages which are undecidable. See the Wikipedia page: Rice's Theorem

    Basically, if you have a set of languages that is non-trivial (i.e., there are TMs that recognize languages in the set, and TMs that recognize languages not in the set), then it is undecidable whether an arbitrary TM's language is in S. For instance, let S be the set consisting of the empty language. Then it is undecidable to determine whether an arbitrary TM accepts the empty language, i.e, no strings. Come up with any non-trivial set of languages, and you have a new undecidable language (all encodings of TMs recognizing languages in the set).