What are all known languages that Turing machines cannot accept?

Question

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

Killiecrankie

Answer 1

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).

Demo

Answer 2

The turing machine accepts all the language even though they are recursively enumerable. Recursive means repeating the same set of rules for any number of times and enumerable means a list of elements. The TM also accepts the computable functions, such as addition, multiplication, subtraction, division, power function, and many more.

Venita