21
$\begingroup$

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.

$\endgroup$
24
$\begingroup$

Since you wanted "strings", I mention the classic one: Post Correspondence Problem.

$\endgroup$
21
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.