Geek Answers Handbook

What are all the famous languages ​​that Turing machines cannot accept?

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

+8
theory turing-machines
source share
1 answer

There are infinitely many languages ​​that no TM can solve. Indeed, the “majority” of languages ​​are unsolvable; there are many solvable languages, but uncountably many languages ​​(hence, uncountably many unsolvable).

Rice's theorem allows you to come up with many examples of languages ​​that are unsolvable. See Wikipedia Page: Rice Theorem

Basically, if you have a set of non-trivial languages ​​(i.e. there are TMs that recognize languages ​​in the set, and TMs that recognize languages ​​in the set), then it is unresolvable whether an arbitrary language TM is in S. For example, let S is a set consisting of an empty language. Then it is impossible to decide whether an arbitrary TM accepts an empty language, i.e. There are no lines. Come up with any non-trivial set of languages, and you have a new insoluble language (all encodings of TMs that recognize languages ​​in the set).

+4
source share

More articles:


All Articles