Is there a “natural” undecidable language?
-
16-10-2019 - |
سؤال
Is there any "natural" language which is undecidable?
by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the language looks like $$ L = \{ \langle M \rangle \mid \ldots \}$$ where $M$ is a TM, DFA (or regular-exp), PDA (or grammar), etc.., then $L$ is not natural. However $L = \{xy \ldots \mid x \text{ is a prefix of y} \ldots \}$ is natural.
المحلول
Since you wanted "strings", I mention the classic one: Post Correspondence Problem.
نصائح أخرى
There are many examples but here are a few:
The set of true sentences in the language of arithmetic is undecidable.
The set of provable sentences in set theory (ZFC) is undecidable.
The set of Diophantine equations which have solutions is undecidable.