# Is there a “natural” undecidable language?

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.

-
Or did I miss something? – Aryabhata Mar 10 '12 at 5:32
How come I didn't think about it?! – Ran G. Mar 10 '12 at 5:51
Excellent example. – Janoma Mar 10 '12 at 6:00
Although Kaveh's answer is more complete, I'll accept this question because it is simple, elegant, and classic! – Ran G. Mar 10 '12 at 18:28
To generalize this answer, also the Tiling problem (aka: domino problem) is undecidable. It can be seen as a natural 2D variant of (the single-dimension) PCP. – Ran G. Feb 26 '13 at 5:53

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.

-