What makes some language theory problems undecidable

摘要

In the theory of automata and formal languages, the undecidability of various properties has been studied for specific classes of languages. Here we abstract the essence of various proofs of undecidability and find wide classes of properties and general conditions on families of languages such that these proofs of undecidability hold. The paper also illustrates the manner in which the degree of undecidability of a property changes as we consider more and more complicated families of languages.