Is there a “natural” undecidable language?
-
16-10-2019 - |
Question
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.
Solution
Since you wanted "strings", I mention the classic one: Post Correspondence Problem.
OTHER TIPS
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.